Spectra of short monadic sentences about sparse random graphs

详细

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.