Geodesic
First-order zero-one law for the uniform model of the random graph
Sbornik. Mathematics, Tome 211 (2020) no. 7, pp. 956-966 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper considers the Erdős-Rényi random graph in the uniform model $G(n,m)$, where $m=m(n)$ is a sequence of nonnegative integers such that $m(n)\sim cn^{\alpha}<(2-\varepsilon)n^2$ for some $c>0$, $\alpha\in[0,2]$, and $\varepsilon>0$. It is shown that $G(n,m)$ obeys the zero-one law for the first-order language if and only if either $\alpha\in\{0,2\}$, or $\alpha$ is irrational, or $\alpha\in(0,1)$ and $\alpha$ is not a number of the form $1-1/\ell$, $\ell\in\mathbb{N}$. Bibliography: 15 titles.
Keywords: zero-one law, first-order logic, uniform model of the random graph. 
@article{SM_2020_211_7_a2,
     author = {M. E. Zhukovskii and N. M. Sveshnikov},
     title = {First-order zero-one law for~the~uniform~model of the random graph},
     journal = {Sbornik. Mathematics},
     pages = {956--966},
     year = {2020},
     volume = {211},
     number = {7},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2020_211_7_a2/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - N. M. Sveshnikov
TI  - First-order zero-one law for the uniform model of the random graph
JO  - Sbornik. Mathematics
PY  - 2020
SP  - 956
EP  - 966
VL  - 211
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/SM_2020_211_7_a2/
LA  - en
ID  - SM_2020_211_7_a2
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A N. M. Sveshnikov
%T First-order zero-one law for the uniform model of the random graph
%J Sbornik. Mathematics
%D 2020
%P 956-966
%V 211
%N 7
%U http://geodesic.mathdoc.fr/item/SM_2020_211_7_a2/
%G en
%F SM_2020_211_7_a2
M. E. Zhukovskii; N. M. Sveshnikov. First-order zero-one law for the uniform model of the random graph. Sbornik. Mathematics, Tome 211 (2020) no. 7, pp. 956-966. http://geodesic.mathdoc.fr/item/SM_2020_211_7_a2/

[1] N. K. Vereschagin, A. Shen, Yazyki i ischisleniya, Lektsii po matematicheskoi logike i teorii algoritmov, 2, MTsNMO, M., 2000, 286 pp. | Zbl

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

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

[4] V. A. Uspenskii, N. K. Vereschagin, V. E. Plisko, Vvodnyi kurs matematicheskoi logiki, Fizmatlit, M., 2007, 128 pp. | 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. Alon, J. H. Spencer, The probabilistic method, Wiley Ser. Discrete Math. Optim., 4th ed., John Wiley Sons, Inc., Hoboken, NJ, 2016, xiv+375 pp. | 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] B. Bollobás, “Threshold functions for small subgraphs”, Math. Proc. Cambridge Philos. Soc., 90:2 (1981), 197–206 | DOI | MR | Zbl

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

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

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

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

[13] A. Ruciński, A. Vince, “Strongly balanced graphs and random graphs”, J. Graph Theory, 10:2 (1986), 251–264 | DOI | MR | Zbl

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

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