On the Zero-One 4-Law for the Erd\H os--R\'enyi Random Graphs
Matematičeskie zametki, Tome 97 (2015) no. 2, pp. 203-216
Voir la notice de l'article provenant de la source Math-Net.Ru
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)$.
Keywords:
zero-one $4$-law, zero-one $k$-law, Erdős–Rényi random graph, first-order property.
@article{MZM_2015_97_2_a3,
author = {M. E. Zhukovskii},
title = {On the {Zero-One} {4-Law} for the {Erd\H} {os--R\'enyi} {Random} {Graphs}},
journal = {Matemati\v{c}eskie zametki},
pages = {203--216},
publisher = {mathdoc},
volume = {97},
number = {2},
year = {2015},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_2015_97_2_a3/}
}
M. E. Zhukovskii. On the Zero-One 4-Law for the Erd\H os--R\'enyi Random Graphs. Matematičeskie zametki, Tome 97 (2015) no. 2, pp. 203-216. http://geodesic.mathdoc.fr/item/MZM_2015_97_2_a3/