On the validity of 0-1 law for shallow first order properties of very sparse random graphs
https://doi.org/10.22405/2226-8383-2024-25-3-299-334
Abstract
In the binomial random graph 𝐺(𝑛, 𝑝) edges between every pair of vertices appear independently with probability 𝑝. The random graph obeys 0-1 𝑘-law, if, for every first order sentence, the probability that 𝐺(𝑛, 𝑝) satisfies it is either 0 or 1 in the limit (as 𝑛 /∞). This paper addresses the following question: given a small 𝑘 and any ℓ, does 𝐺(𝑛, 𝑛−𝑙−1/ℓ) satisfy 0-1 𝑘-law? We answer this question for 𝑘 = 3 and all ℓ. We also prove that for 𝑘 = 4 and ℓ ∈ [1, 40] ∪ {72} 0-1 𝑘-law does not hold.
About the Author
Rufina Ruslanovna Shefrukova
Adyghe State University
Russian Federation
Russian Federation
postgraduate student
References
1. Vereshchagin, N.K., Shen, A. 2012, “Languages and calculus”, MCCME, 4th ed, P. 240.
2. Zhukovsky, M.E., Ostrovskii, L.B. 2017, “First-order properties of bounded quantor depth of strongly sparse random graphs”, Izvestiya:Mathematics, Vol. 81, pp. 100–113.
3. Bollob´as, В. 1981, “Threshold functions for small subgraphs”, Math. Proc. Camb. Phil. Soc., pp. 197–206.
4. Ehrenfeucht, А. 1960, “Anapplication of games to the completeness problem for formalized theories”, Warszawa, Fund.Math., pp. 121–149.
5. Erd˝os P., R´enyi, A. 1959, “On Random Graphs”, Publicationes Mathematicae (Debrecen), Vol. 6, pp. 290–297.
6. Erd˝os, P., R´enyi, A. 1960, “On the evolution of random graphs”, Publ. Math. Inst. Hungar. Acad. Sci., pp. 17–61.
7. Fagin, R. 1976, “Probabilities in Finite Models”, J. Symbolic Logic, Vol. 41, pp. 50–58.
8. Glebskii, Y.V., Kogan, D.I., Liogon’kii, M.I., Talanov, V.A. 1969, “Range and degree of
9. realizability of formulas in the restricted predicate calculus”, Cybern Syst Anal., Vol. 5, pp.
10. –154.
11. Libkin, L. 2004, “Elements of finite model theory”, Texts in Theoretical Computer Science. An EATCS Series, Springer.
12. Ostrovsky, L.B., Zhukovskii, M. E. 2017, “Monadic second-order properties of very sparse random graphs”, Annals of pure and applied logic, Vol. 168, pp. 2087–2101.
13. Shelah, S., Spencer, J.H. 1988, “Zero-One Laws for Sparse Random Graphs”, J.Amer. Math. Soc., Vol. 1, pp. 97–115.
14. Spencer, J.H. 1991, “Threshold spectra via the Ehrenfeucht game”, Discrete Applied Math., Vol. 30, pp. 235–252.
15. Verbitsky, О., Zhukovskii, М. 2019, “On the First-Order Complexity of Induced Subgraph Isomorphism”, Logical Methods in Computer Science, Vol. 15, pp. 25:1–25:24.
16. Verbitsky, О., Zhukovskii, М. 2019, “The Descriptive Complexity of Subgraph Isomorphism without Numerics”, Theory of Computing Systems, Vol. 63, pp. 902–921.
17. Zhukovskii, M.E. 2017, “On the zero–one 𝑘-law extensions”, European Journal of Combinatorics, Vol. 60, pp. 66–81.
18. Zhukovskii, M.E. 2012, “Zero-one 𝑘-law”, Discrete Mathematics, Vol. 312, pp. 1670–1688.
Review
For citations:
Shefrukova R.R. On the validity of 0-1 law for shallow first order properties of very sparse random graphs. Chebyshevskii Sbornik. 2024;25(3):299-334. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-3-299-334
Views:
225
Email this article 