Spectra of short monadic sentences about sparse random graphs |
| |
| Authors: | M E Zhukovskii A B Kupavskii |
| |
| Institution: | 1.Moscow Institute of Physics and Technology (State University),Dolgoprudnyi, Moscow oblast,Russia;2.RUDN University,Moscow,Russia;3.University Grenoble-Alpes,Grenoble,France |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
