Email this article Spectra of short monadic sentences about sparse random graphs
- Authors: Zhukovskii M.E.1,2, Kupavskii A.B.1,3
-
Affiliations:
- Moscow Institute of Physics and Technology (State University)
- RUDN University
- University Grenoble-Alpes
- Issue: Vol 95, No 1 (2017)
- Pages: 60-61
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/224763
- DOI: https://doi.org/10.1134/S1064562417010227
- ID: 224763
Cite item
Open Access
Access granted
Subscription Access
Abstract
A random graph G(n, p) is said to obey the (monadic) zero–one k-law if, for any monadic formula of quantifier depth k, the probability that it is true for the random graph tends to either zero or one. In this paper, following J. Spencer and S. Shelah, we consider the case p = n−α. It is proved that the least k for which there are infinitely many α such that a random graph does not obey the zero–one k-law is equal to 4.
About the authors
M. E. Zhukovskii
Moscow Institute of Physics and Technology (State University); RUDN University
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 117198
A. B. Kupavskii
Moscow Institute of Physics and Technology (State University); University Grenoble-Alpes
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700; Grenoble
Supplementary files
