Geodesic
The largest critical point in the zero-one $k$-law
Sbornik. Mathematics, Tome 206 (2015) no. 4, pp. 489-509 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The largest value of $\alpha<1$ 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},
     year = {2015},
     volume = {206},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2015_206_4_a1/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
TI  - The largest critical point in the zero-one $k$-law
JO  - Sbornik. Mathematics
PY  - 2015
SP  - 489
EP  - 509
VL  - 206
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/SM_2015_206_4_a1/
LA  - en
ID  - SM_2015_206_4_a1
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%T The largest critical point in the zero-one $k$-law
%J Sbornik. Mathematics
%D 2015
%P 489-509
%V 206
%N 4
%U http://geodesic.mathdoc.fr/item/SM_2015_206_4_a1/
%G en
%F 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/

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

[2] M. E. Zhukovskii, “Zero-one laws for first-order formulas with a bounded quantifier depth”, Dokl. Math., 83:1 (2011), 8–11 | DOI | MR | Zbl

[3] M. 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), 119–155 | MR | Zbl

[4] M. E. Zhukovskii, “On the zero-one $k$-law extensions”, Proc. of RS (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] S. Janson, T. Łuczak, A. Rucinski, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000, xii+333 pp. | DOI | MR | Zbl

[7] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp. | DOI | MR | Zbl

[8] V. F. Kolchin, Random graphs, Encyclopedia Math. Appl., 53, Cambridge Univ. Press, Cambridge, 1999, xii+252 pp. | MR | MR | Zbl | Zbl

[9] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 2nd ed., Wiley-Interscience [John Wiley Sons], New York, 2000, xviii+301 pp. | DOI | MR | Zbl

[10] A. M. Raigorodskii, Modeli sluchainykh grafov, MTsNMO, M., 2011, 136 pp.

[11] N. K. Vereschagin, A. Shen, Yazyki i ischisleniya, MTsNMO, M., 2000, 286 pp.

[12] V. A. Uspenskii, N. K. Vereschagin, V. E. Plisko, Vvodnyi kurs matematicheskoi logiki, Fizmatlit, M., 2007, 128 pp. | Zbl

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

[14] J. Spencer, The strange logic of random graphs, Algorithms Combin., 22, Springer-Verlag, Berlin, 2001, x+168 pp. | DOI | MR | Zbl

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

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

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