Geodesic
When Does the Zero-One $k$-Law Fail?
Matematičeskie zametki, Tome 99 (2016) no. 3, pp. 342-349.

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. 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$.
Keywords: zero-one $k$-law, Erdős–Rényi random graph, first-order property. 
@article{MZM_2016_99_3_a2,
     author = {M. E. Zhukovskii and A. E. Medvedeva},
     title = {When {Does} the {Zero-One} $k${-Law} {Fail?}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {342--349},
     publisher = {mathdoc},
     volume = {99},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a2/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - A. E. Medvedeva
TI  - When Does the Zero-One $k$-Law Fail?
JO  - Matematičeskie zametki
PY  - 2016
SP  - 342
EP  - 349
VL  - 99
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a2/
LA  - ru
ID  - MZM_2016_99_3_a2
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A A. E. Medvedeva
%T When Does the Zero-One $k$-Law Fail?
%J Matematičeskie zametki
%D 2016
%P 342-349
%V 99
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a2/
%G ru
%F MZM_2016_99_3_a2
M. E. Zhukovskii; A. E. Medvedeva. When Does the Zero-One $k$-Law Fail?. Matematičeskie zametki, Tome 99 (2016) no. 3, pp. 342-349. http://geodesic.mathdoc.fr/item/MZM_2016_99_3_a2/

[1] S. Janson, T. Łuczak, A. Rucinski, Random Graphs, Wiley-Intersci. Ser. Discrete Math. Optim., New York, Wiley, 2000 | MR | Zbl

[2] M. E. Zhukovskii, A. M. Raigorodskii, “Sluchainye grafy: modeli i predelnye kharakteristiki”, UMN, 70:1 (2015), 35–88 | DOI | MR | Zbl

[3] N. K. Vereschagin, A. Shen, Yazyki i ischisleniya, MTsNMO, M., 2000

[4] M. E. Zhukovskii, “Zakony nulya ili edinitsy dlya formul pervogo poryadka s ogranichennoi kvantornoi glubinoi”, Dokl. RAN, 436:1 (2011), 14–18 | MR | Zbl

[5] M. Zhukovskii, “Zero-one $k$-law”, Discrete Math., 312:10 (2012), 1670–1688 | DOI | MR | Zbl

[6] M. E. Zhukovskii, “Rasshirenie $k$-zakona nulya ili edinitsy”, Dokl. RAN, 454:1 (2014), 23–26 | DOI | MR | Zbl

[7] M. E. Zhukovskii, “O naibolshei kriticheskoi tochke v $k$-zakone nulya ili edinitsy”, Matem. sb., 206:4 (2015), 13–34 | DOI | MR | Zbl

[8] S. Shelah, J. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1 (1988), 97–115 | DOI | MR | Zbl

[9] Yu. V. Glebskii, D. I. Kogan, M. I. Liogonkii, V. A. Talanov, “Ob'em i dolya vypolnimosti formul uzkogo ischisleniya predikatov”, Kibernetika, 1969, no. 2, 17–27 | MR | Zbl

[10] R. Fagin, “Probabilities in finite models”, J. Symbolic Logic, 41:1 (1976), 50–58 | DOI | MR | Zbl

[11] B. Bollobás, “Threshold functions for small subgraphs”, Math. Proc. Cambridge Philos. Soc., 90:2 (1981), 197–206 | DOI | MR | Zbl