On the Zero-One 4-Law for the Erd\H os--R\'enyi Random Graphs

M. E. Zhukovskii

Matematičeskie zametki, Tome 97 (2015) no. 2, pp. 203-216

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. Earlier, the author obtained zero-one $k$-laws for any positive integer $k\ge 3$, which describe the behavior of the probabilities of the first-order properties expressed by formulas of quantifier depth bounded by $k$ for $\alpha$ in the interval $(0,1/(k-2)]$ and $k\ge 4$ in the interval $(1-1/2^{k-1},1)$. This result is improved for $k=4$. Moreover, it is proved that, for any $k\ge 4$, the zero-one $k$-law does not hold at the lower boundary of the interval $(1-1/2^{k-1},1)$.

Détail

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