О справедливости закона 0 или 1 для неглубоких свойств первого порядка сильно разреженного случайного графа
https://doi.org/10.22405/2226-8383-2024-25-3-299-334
Аннотация
В биномиальном случайном графе 𝐺(𝑛, 𝑝) ребра проводятся независимо и с вероятностью 𝑝 каждое. Случайный граф подчиняется 𝑘-закону 0 или 1, если вероятность истинности любой формулы первого порядка, кванторная глубина которой не превосходит 𝑘, стремится либо к 0 либо к 1 при 𝑛 /∞. Данная статья посвящена ответу на следующий вопрос: для каких пар 𝑘 и ℓ случайный граф 𝐺(𝑛, 𝑛−𝑙−1/ℓ) подчиняется 𝑘-закону 0 или 1? Мы получили полный ответ при 𝑘 = 3 и всех натуральных ℓ, а также доказали, что при 𝑘 = 4 и ℓ ∈ [1, 40] ∪ {72} закон нарушается.
Список литературы
1. Верещагин, Н.К., Шень, А. Языки и исчисления // МЦНМО. 2012. 4-е изд. С. 240.
2. Жуковский, М.Е., Островский, Л.Б. Свойства первого порядка ограниченной кванторной глубины сильно разреженных случайных графов // Изв. РАН. Сер. матем.- 2017.- Вып. 81.- С. 100–113.
3. Bollob´as, В. Threshold functions for small subgraphs // Math. Proc. Camb. Phil. Soc. 1981. P. 197–206.
4. Ehrenfeucht, А. Anapplication of games to the completeness problem for formalized theories // Warszawa, Fund.Math. 1960. P. 121–149.
5. Erd˝os, P., R´enyi, A. On Random Graphs // Publicationes Mathematicae (Debrecen). 1959. Vol. 6. P. 290–297.
6. Erd˝os, P., R´enyi, A. On the evolution of random graphs // Publ. Math. Inst. Hungar. Acad. Sci. 1960. P. 17–61.
7. Fagin, R. Probabilities in Finite Models // J. Symbolic Logic. 1976. Vol. 41. P. 50–58.
8. Глебский, Ю.В., Коган, Д.И., Легонький, М.И., Таланов, В.А. Объем и доля выполнимости формул узкого исчисления предикатов // Кибернетика 1969. Т. 2. С. 17–26.
9. Libkin, L. Elements of finite model theory // Texts in Theoretical Computer Science. An
10. EATCS Series, Springer. 2004.
11. Ostrovsky, L.B., Zhukovskii, M.E. Monadic second-order properties of very sparse random graphs // Annals of pure and applied logic. 2017. Vol. 168. P. 2087–2101.
12. Shelah, S., Spencer, J.H. Zero-One Laws for Sparse Random Graphs // J.Amer. Math. Soc. 1988. Vol. 1. P. 97–115.
13. Spencer, J.H. Threshold spectra via the Ehrenfeucht game // Discrete Applied Math. 1991. Vol. 30. P. 235–252.
14. Verbitsky, О., Zhukovskii, М. On the First-Order Complexity of Induced Subgraph Isomorphism // Logical Methods in Computer Science. 2019. Vol. 15. P. 25:1–25:24.
15. Verbitsky, О., Zhukovskii, М. The Descriptive Complexity of Subgraph Isomorphism without Numerics // Theory of Computing Systems. 2019. Vol. 63. P. 902–921.
16. Zhukovskii, M.E. On the zero–one 𝑘-law extensions // European Journal of Combinatorics. 2017. Vol. 60. P. 66–81.
17. Zhukovskii, M.E. Zero-one 𝑘-law // Discrete Mathematics. 2012. Vol. 312. P. 1670–1688.
Рецензия
Для цитирования:
Шефрукова Р.Р. О справедливости закона 0 или 1 для неглубоких свойств первого порядка сильно разреженного случайного графа. Чебышевский сборник. 2024;25(3):299-334. https://doi.org/10.22405/2226-8383-2024-25-3-299-334
For citation:
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
Просмотров:
226
Послать статью по эл. почте 