RUS  ENG
Полная версия
ЖУРНАЛЫ // Доклады Российской академии наук. Математика, информатика, процессы управления // Архив

Докл. РАН. Матем., информ., проц. упр., 2021, том 500, страницы 31–34 (Mi danma200)

МАТЕМАТИКА

О 4-спектре свойств первого порядка случайных графов

М. Е. Жуковскийabcd, А. Д. Матушкинa, Ю. Н. Яровиковae

a Московский физико-технический институт (национальный исследовательский университет), Долгопрудный, Московская обл., Россия
b Российская академия народного хозяйства и государственной службы при Президенте Российской Федерaции, Москва, Россия
c Кавказский математический центр Адыгейского государственного университета, Майкоп, Россия
d Московский центр фундаментальной и прикладной математики, Москва, Россия
e Институт искусственного интеллекта AIRI, Москва, Россия

Аннотация: $k$-Спектром называется множество таких положительных чисел $\alpha$, что биномиальный случайный граф $G(n,n^{-\alpha})$ не подчиняется закону нуля или единицы для формул первого порядка кванторной глубины не более $k$. Мы доказали, что минимальное $k$, при котором $k$-спектр бесконечен, равно 5.

Ключевые слова: логика первого порядка, биномиальный случайный граф, закон нуля или единицы, спектр формулы, игра Эренфойхта.

УДК: 519.175.4

Статья представлена к публикации: В. В. Козлов
Поступило: 27.04.2021
После доработки: 07.07.2021
Принято к публикации: 18.08.2021

DOI: 10.31857/S2686954321050180


 Англоязычная версия: Doklady Mathematics, 2021, 104:2, 247–249

Реферативные базы данных:


© МИАН, 2024