Universal Zero-One $k$-Law

M. E. Zhukovskii ; A. D. Matushkin

Matematičeskie zametki, Tome 99 (2016) no. 4, pp. 511-525.

Résumé

The limit probabilities of first-order properties of a random graph in the Erdős–Rényi model $G(n, n^{-\alpha})$, $\alpha\in (0, 1)$, are studied. For any positive integer $k \ge 4$ and any rational number $t/s \in (0, 1)$, an interval with right endpoint $t/s$ is found in which the zero-one $k$-law holds (the zero-one $k$-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most $k$). Moreover, it is proved that, for rational numbers $t/s$ with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as $n \to\infty$) as that of the length of the maximal interval with right endpoint $t/s$ in which the zero-one $k$-law holds.

Détail

Keywords: zero-one $k$-law, Erdős–Rényi random graph, first-order property.

Bibliographie

[1] M. E. Zhukovskii, A. M. Raigorodskii, “Sluchainye grafy: modeli i predelnye kharakteristiki”, UMN, 70:1 (2015), 35–88 | DOI | MR | Zbl

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

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

[4] S. Janson, T. Łuczak, A. Rucinski, Random Graphs, Wiley-Interscience, New York, 2000 | MR | Zbl

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

[6] V. F. Kolchin, Sluchainye grafy, Teoriya veroyatnostei i matematicheskaya statistika, Fizmatlit, M., 2000 | MR | Zbl

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

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

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

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

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

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

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

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

[15] M. E. Zhukovskii, “Rasshirenie $k$-zakona nulya ili edinitsy”, Dokl. RAN, 454:1 (2014), 23–26 | DOI | MR | Zbl

[16] M. E. Zhukovskii, “O naibolshei kriticheskoi tochke v $k$-zakone nulya ili edinitsy”, Matem. sb., 206:4 (2015), 13–34 | DOI | MR | Zbl

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

[18] A. Ruciński, A. Vince, “Balanced graphs and the problem of subgraphs of a random graph”, Congr. Numer, 49 (1985), 181–190 | MR | Zbl

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

[20] M. E. Zhukovskii, “O 4-zakone nulya ili edinitsy dlya sluchainogo grafa Erdesha–Reni”, Matem. zametki, 97:2 (2015), 203–216 | DOI | MR | Zbl

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

[22] J. H. Spencer, M. E. Zhukovskii, “Spectra for random graphs of fixed quantifier depth”, Discrete Math., 2015 (to appear)

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