Geodesic
On the 4-spectrum of first-order properties of random graphs
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 500 (2021), pp. 31-34.

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

A $k$-spectrum is a set of all positive $\alpha$ such that the random binomial graph $G(n,n^{-\alpha})$ does not obey the zero–one law for first-order formulas with a quantifier depth at most $k$. We have proved that the minimal $k$ such that the $k$-spectrum is infinite equals 5.
Keywords: first-order logic, random binomial graph, zero–one law, spectrum of formula, Ehrenfeucht–Fraïssé game. 
@article{DANMA_2021_500_a5,
     author = {M. E. Zhukovskii and A. D. Matushkin and Yu. N. Yarovikov},
     title = {On the 4-spectrum of first-order properties of random graphs},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {31--34},
     publisher = {mathdoc},
     volume = {500},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2021_500_a5/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - A. D. Matushkin
AU  - Yu. N. Yarovikov
TI  - On the 4-spectrum of first-order properties of random graphs
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2021
SP  - 31
EP  - 34
VL  - 500
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DANMA_2021_500_a5/
LA  - ru
ID  - DANMA_2021_500_a5
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A A. D. Matushkin
%A Yu. N. Yarovikov
%T On the 4-spectrum of first-order properties of random graphs
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2021
%P 31-34
%V 500
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DANMA_2021_500_a5/
%G ru
%F DANMA_2021_500_a5
M. E. Zhukovskii; A. D. Matushkin; Yu. N. Yarovikov. On the 4-spectrum of first-order properties of random graphs. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 500 (2021), pp. 31-34. http://geodesic.mathdoc.fr/item/DANMA_2021_500_a5/

[1] Vereschagin N.K., Shen A., Yazyki i ischisleniya, MNTsMO, M., 2012, 240 pp.

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

[3] Fagin R., “Probabilities in finite models”, J. Symbolic Logic, 1976, no. 41, 50–58 | DOI | MR | Zbl

[4] Spencer J.H., The Strange Logic of Random Graphs, Springer-Verlag, Berlin, 2001, 168 pp. | MR | Zbl

[5] Spencer J.H., “Threshold spectra via the Ehrenfeucht game”, Discrete Applied Mathematics, 1991, no. 30, 235–252 | DOI | MR | Zbl

[6] Ehrenfeucht A., “An application of games to the completness problem for formalized theories”, Warszawa Fund. Math., 1960, no. 49, 121–149 | MR

[7] Alon N., Spencer J.H., Probabilistic method, Wiley, New York, 2008, 400 pp. | MR | Zbl

[8] Janson S., Łuczak T., Ruciński A., Random Graphs, Wiley, New York, 2000, 336 pp. | MR | Zbl

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

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

[11] Ostrovsky L.B., Zhukovskii M.E., “Monadic second-order properties of very sparse random graphs”, Annals of pure and applied logic, 168:11 (2017), 2087–2101 | DOI | MR | Zbl

[12] Spencer J.H. Infinite spectra in the first order theory of graphs, Combinatorica, 10:1 (1990), 95–102 | DOI | MR | Zbl

[13] Zhukovskii M., “On Infinite Spectra of First Order Properties of Random Graphs”, Moscow Journal of Combinatorics and Number Theory, 6:4 (2016), 73–102 | MR | Zbl

[14] Matushkin A.D., Zhukovskii M.E., “First order sentences about random graphs: small number of alternations”, Discrete Applied Mathematics, 236 (2018), 329–346 | DOI | MR | Zbl