The largest critical point in the zero-one $k$-law
Sbornik. Mathematics, Tome 206 (2015) no. 4, pp. 489-509
Voir la notice de l'article provenant de la source Math-Net.Ru
The largest value of $\alpha1$ is established for which the random graph $G(n,n^{-\alpha})$ does not obey the zero-one $k$-law for first-order properties. As was already known, the zero-one $k$-law is valid for all $\alpha>1-1/(2^{k}-2)$ with the exception of $1-1/(2^{k}-1)$, $1-1/2^{k}$. For $\alpha=1-1/(2^k-2)$ the law fails. In this work, it is shown that the law is valid for $\alpha\in\{1-1/(2^{k}-1),1-1/2^{k}\}$.
Bibliography: 17 titles.
Keywords:
zero-one law, random graph, first-order properties, the Ehrenfeucht game, bounded quantifier depth.
@article{SM_2015_206_4_a1,
author = {M. E. Zhukovskii},
title = {The largest critical point in the zero-one $k$-law},
journal = {Sbornik. Mathematics},
pages = {489--509},
publisher = {mathdoc},
volume = {206},
number = {4},
year = {2015},
language = {en},
url = {http://geodesic.mathdoc.fr/item/SM_2015_206_4_a1/}
}
M. E. Zhukovskii. The largest critical point in the zero-one $k$-law. Sbornik. Mathematics, Tome 206 (2015) no. 4, pp. 489-509. http://geodesic.mathdoc.fr/item/SM_2015_206_4_a1/