Geodesic
First-order properties of bounded quantifier depth of very sparse random graphs
Izvestiya. Mathematics , Tome 81 (2017) no. 6, pp. 1155-1167.

Voir la notice de l'article provenant de la source Math-Net.Ru

We say that a random graph obeys the zero-one $k$-law if every property expressed by a first-order formula with quantifier depth at most $k$ holds with probability tending to $0$ or $1$. It is known that the random graph $G(n,n^{-\alpha})$ obeys the zero-one $k$-law for every $k\in\mathbb{N}$ and every positive irrational $\alpha$, as well as for all rational $\alpha>1$ which are not of the form $1+1/l$ (for any positive integer $l$). It is also known that for all other rational positive $\alpha$, the random graph does not obey the zero-one $k$-law for sufficiently large $k$. In this paper we put $\alpha=1+1/l$ and obtain upper and lower bounds for the largest $k$ such that the zero-one $k$-law holds.
Keywords: Erdős–Rényi random graph, first-order properties, zero-one law, Ehrenfeucht game. 
@article{IM2_2017_81_6_a5,
     author = {M. E. Zhukovskii and L. B. Ostrovskii},
     title = {First-order properties of bounded quantifier depth of very sparse random graphs},
     journal = {Izvestiya. Mathematics },
     pages = {1155--1167},
     publisher = {mathdoc},
     volume = {81},
     number = {6},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2017_81_6_a5/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - L. B. Ostrovskii
TI  - First-order properties of bounded quantifier depth of very sparse random graphs
JO  - Izvestiya. Mathematics 
PY  - 2017
SP  - 1155
EP  - 1167
VL  - 81
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2017_81_6_a5/
LA  - en
ID  - IM2_2017_81_6_a5
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A L. B. Ostrovskii
%T First-order properties of bounded quantifier depth of very sparse random graphs
%J Izvestiya. Mathematics 
%D 2017
%P 1155-1167
%V 81
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2017_81_6_a5/
%G en
%F IM2_2017_81_6_a5
M. E. Zhukovskii; L. B. Ostrovskii. First-order properties of bounded quantifier depth of very sparse random graphs. Izvestiya. Mathematics , Tome 81 (2017) no. 6, pp. 1155-1167. http://geodesic.mathdoc.fr/item/IM2_2017_81_6_a5/

[1] S. Janson, T. Łuczak, A. Ruciński, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience [John Wiley Sons], New York, 2000, xii+333 pp. | DOI | MR | Zbl

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

[3] 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

[4] M. E. Zhukovskii, A. M. Raigorodskii, “Random graphs: models and asymptotic characteristics”, Russian Math. Surveys, 70:1 (2015), 33–81 | DOI | DOI | MR | Zbl

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

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

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

[8] 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

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

[10] M. E. Zhukovskii, “Extension of the zero-one $k$-law”, Dokl. Math., 89:1 (2014), 16–19 | DOI | DOI | MR | Zbl

[11] M. E. Zhukovskii, “The largest critical point in the zero-one $k$-law”, Sb. Math., 206:4 (2015), 489–509 | DOI | DOI | MR | Zbl

[12] M. E. Zhukovskii, “On the zero-one 4-law for the Erdős–Rényi random graphs”, Math. Notes, 97:2 (2015), 190–200 | DOI | DOI | MR | Zbl

[13] M. E. Zhukovskii, A. D. Matushkin, “Universal zero-one $k$-law”, Math. Notes, 99:4 (2016), 511–523 | DOI | DOI | MR | Zbl

[14] M. E. Zhukovskii, A. E. Medvedeva, “When does the zero-one $k$-law fail?”, Math. Notes, 99:3 (2016), 362–367 | DOI | DOI | MR | Zbl

[15] O. Pikhurko, J. Spencer, O. Verbitsky, “Succinct definitions in the first order theory of graphs”, Ann. Pure Appl. Logic, 139:1-3 (2006), 74–109 | DOI | MR | Zbl

[16] 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

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

[18] J. Spencer, “Threshold functions for extension statements”, J. Combin. Theory Ser. A, 53:2 (1990), 286–305 | DOI | MR | Zbl

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

[20] O. Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ., Amer. Math. Soc., Providence, R.I., 1962, x+270 pp. | MR | MR | Zbl | Zbl