Universal Zero-One $k$-Law

M. E. Zhukovskii ; A. D. Matushkin

Matematičeskie zametki, Tome 99 (2016) no. 4, pp. 511-525

Résumé

The limit probabilities of first-order properties of a random graph in the Erdős–Rényi model $G(n, n^{-\alpha})$, $\alpha\in (0, 1)$, are studied. For any positive integer $k \ge 4$ and any rational number $t/s \in (0, 1)$, an interval with right endpoint $t/s$ is found in which the zero-one $k$-law holds (the zero-one $k$-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most $k$). Moreover, it is proved that, for rational numbers $t/s$ with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as $n \to\infty$) as that of the length of the maximal interval with right endpoint $t/s$ in which the zero-one $k$-law holds.

Détail

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