Enviar artigo por via de e-mail Spectra of short monadic sentences about sparse random graphs
- Autores: Zhukovskii M.E.1,2, Kupavskii A.B.1,3
-
Afiliações:
- Moscow Institute of Physics and Technology (State University)
- RUDN University
- University Grenoble-Alpes
- Edição: Volume 95, Nº 1 (2017)
- Páginas: 60-61
- Seção: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/224763
- DOI: https://doi.org/10.1134/S1064562417010227
- ID: 224763
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Sobre autores
M. Zhukovskii
Moscow Institute of Physics and Technology (State University); RUDN University
Autor responsável pela correspondência
Email: zhukmax@gmail.com
Rússia, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 117198
A. Kupavskii
Moscow Institute of Physics and Technology (State University); University Grenoble-Alpes
Email: zhukmax@gmail.com
Rússia, Dolgoprudnyi, Moscow oblast, 141700; Grenoble
Arquivos suplementares
