Email this article First-order zero-one law for the uniform model of the random graph
- Authors: Zhukovskii M.E.1,2, Sveshnikov N.M.3
-
Affiliations:
- Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University)
- Moscow Center for Fundamental and Applied Mathematics
- Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology (National Research University)
- Issue: Vol 211, No 7 (2020)
- Pages: 60-71
- Section: Articles
- URL: https://bakhtiniada.ru/0368-8666/article/view/133335
- DOI: https://doi.org/10.4213/sm9321
- ID: 133335
Cite item
Open Access
Access granted
Subscription Access
Abstract
The paper considers the Erdős-Renyi random graph in the uniform model $G(n,m)$, where $m=m(n)$ is a sequence of nonnegative integers such that $m(n)\sim cn^{\alpha}<(2-\varepsilon)n^2$ for some $c>0$, $\alpha\in[0,2]$, and $\varepsilon>0$. It is shown that $G(n,m)$ obeys the zero-one law for the first-order language if and only if either $\alpha\in\{0,2\}$, or $\alpha$ is irrational, or $\alpha\in(0,1)$ and $\alpha$ is not a number of the form $1-1/\ell$, $\ell\in\mathbb{N}$. Bibliography: 15 titles.
About the authors
Maksim Evgen'evich Zhukovskii
Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University); Moscow Center for Fundamental and Applied Mathematics
Email: zhukmax@gmail.com
Doctor of physico-mathematical sciences
Nikita Maksimovich Sveshnikov
Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology (National Research University)
References
- Н. К. Верещагин, А. Шень, Языки и исчисления, Лекции по математической логике и теории алгоритмов, 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
Supplementary files
