When Does the Zero-One $k$-Law Fail?

M. E. Zhukovskii ; A. E. Medvedeva

Matematičeskie zametki, Tome 99 (2016) no. 3, pp. 342-349

Résumé

The limit probabilities of the first-order properties of a random graph in the Erdős–Rényi model $G(n,n^{-\alpha})$, $\alpha\in(0,1)$, are studied. A random graph $G(n,n^{-\alpha})$ is said to obey the zero-one $k$-law if, given any property expressed by a formula of quantifier depth at most $k$, the probability of this property tends to either 0 or 1. As is known, for $\alpha=1-1/(2^{k-1}+a/b)$, where $a>2^{k-1}$, the zero-one $k$-law holds. Moreover, this law does not hold for $b=1$ and $a \le 2^{k-1}-2$. It is proved that the $k$-law also fails for $b>1$ and $a \le 2^{k-1}-(b+1)^2$.

Détail

Keywords: zero-one $k$-law, Erdős–Rényi random graph, first-order property.