Отправить статью по E-mail Закон нуля или единицы первого порядка для равномерной модели случайного графа
- Авторы: Жуковский М.Е.1,2, Свешников Н.М.3
-
Учреждения:
- Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет)
- Московский центр фундаментальной и прикладной математики
- Физтех-школа прикладной математики и информатики, Московский физико-технический институт (национальный исследовательский университет)
- Выпуск: Том 211, № 7 (2020)
- Страницы: 60-71
- Раздел: Статьи
- URL: https://journals.rcsi.science/0368-8666/article/view/133335
- DOI: https://doi.org/10.4213/sm9321
- ID: 133335
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Рассматривается случайный граф Эрдёша–Реньи в равномерной модели $G(n,m)$, где $m=m(n)$ – такая последовательность целых неотрицательных чисел, что $m(n)\sim cn^{\alpha}<(2-\varepsilon)n^2$ для некоторых $c>0$, $\alpha\in[0,2]$ и $\varepsilon>0$. Доказано, что $G(n,m)$ подчиняется закону нуля или единицы для языка первого порядка тогда и только тогда, когда либо $\alpha\in\{0,2\}$, либо $\alpha$ иррационально, либо $\alpha\in(0,1)$ и $\alpha$ не принадлежит множеству чисел вида $1-1/\ell$, $\ell\in\mathbb{N}$.Библиография: 15 названий.
Об авторах
Максим Евгеньевич Жуковский
Лаборатория продвинутой комбинаторики и сетевых приложений, Московский физико-технический институт (национальный исследовательский университет); Московский центр фундаментальной и прикладной математики
Email: zhukmax@gmail.com
доктор физико-математических наук
Никита Максимович Свешников
Физтех-школа прикладной математики и информатики, Московский физико-технический институт (национальный исследовательский университет)
Список литературы
- Н. К. Верещагин, А. Шень, Языки и исчисления, Лекции по математической логике и теории алгоритмов, 2, МЦНМО, М., 2000, 286 с.
- Ю. В. Глебский, Д. И. Коган, М. И. Лиогонький, В. А. Таланов, “Объем и доля выполнимости формул узкого исчисления предикатов”, Кибернетика, 1969, № 2, 17–27
- М. Е. Жуковский, А. М. Райгородский, “Случайные графы: модели и предельные характеристики”, УМН, 70:1(421) (2015), 35–88
- В. А. Успенский, Н. К. Верещагин, В. Е. Плиско, Вводный курс математической логики, Физматлит, М., 2007, 128 с.
- J. Spencer, The strange logic of random graphs, Algorithms Combin., 22, Springer-Verlag, Berlin, 2001, x+168 pp.
- N. Alon, J. H. Spencer, The probabilistic method, Wiley Ser. Discrete Math. Optim., 4th ed., John Wiley & Sons, Inc., Hoboken, NJ, 2016, xiv+375 pp.
- B. Bollobas, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp.
- B. Bollobas, “Threshold functions for small subgraphs”, Math. Proc. Cambridge Philos. Soc., 90:2 (1981), 197–206
- A. Ehrenfeucht, “An application of games to the completeness problem for formalized theories”, Fund. Math., 49 (1960/1961), 129–141
- P. Erdős, A. Renyi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutato Int. Közl., 5 (1960), 17–61
- R. Fagin, “Probabilities on finite models”, J. Symbolic Logic, 41:1 (1976), 50–58
- S. Janson, T. Łuczak, A. Rucinski, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience [John Wiley & Sons], New York, 2000, xii+333 pp.
- A. Rucinski, A. Vince, “Strongly balanced graphs and random graphs”, J. Graph Theory, 10:2 (1986), 251–264
- S. Shelah, J. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1:1 (1988), 97–115
- J. Spencer, “Counting extensions”, J. Combin. Theory Ser. A, 55:2 (1990), 247–255
Дополнительные файлы
