Geodesic
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/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
TI  - On the Zero-One 4-Law for the Erd\H os--R\'enyi Random Graphs
JO  - Matematičeskie zametki
PY  - 2015
SP  - 203
EP  - 216
VL  - 97
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2015_97_2_a3/
LA  - ru
ID  - MZM_2015_97_2_a3
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%T On the Zero-One 4-Law for the Erd\H os--R\'enyi Random Graphs
%J Matematičeskie zametki
%D 2015
%P 203-216
%V 97
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2015_97_2_a3/
%G ru
%F 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/

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

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

[3] M. E. Zhukovskii, “On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth”, Moscow J. Combin. Number Theory, 4:2 (2014)

[4] M. E. Zhukovskii, “On the zero-one $k$-law extensions”, Proc. of the 16th International Conference “Random Structures and Algorithms” (Poznań, August 5–9, 2013) (to appear)

[5] P. Erdős, A. Rényi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17–61 | MR | Zbl

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

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

[8] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[9] V. F. Kolchin, Sluchainye grafy, 2-e izdanie, Fizmatlit, M., 2004

[10] N. Alon, Dzh. Spenser, Veroyatnostnyi metod, Binom. Laboratoriya znanii, M., 2007 | MR | Zbl

[11] A. M. Raigorodskii, Modeli sluchainykh grafov, MTsNMO, M., 2011

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

[13] V. A. Uspenskii, N. K. Vereschagin, V. E. Plisko, Vvodnyi kurs matematicheskoi logiki, Fizmatlit, M., 1997

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

[15] J. Spencer, The Strange Logic of Random Graphs, Algorithms Combin., 22, Springer-Verlag, Berlin, 2001 | MR | Zbl

[16] M. McArthur, “The asymptotic behavior of $L^k_{\infty,\omega}$ on sparse random graphs”, Logic and Random Structures, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 33, Amer. Math. Soc., Providence, RI, 1997, 53–63 | MR | Zbl

[17] M. E. Zhukovskii, “O naibolshei kriticheskoi tochke v $k$-zakone nulya ili edinitsy”, Matem. sb. (to appear)

[18] J. H. Spencer, “Counting extensions”, J. Combin. Theory Ser. A, 55:2 (1990), 247–255 | DOI | MR | Zbl

[19] A. Ehrenfeucht, “An application of games to the completness problem for formalized theories”, Fund. Math., 49 (1960), 129–141 | MR | Zbl