Email this article A disproof of the zero-one law for existential monadic second order properties of sparse binomial random graphs
- Authors: Egorova A.N.1, Zhukovskii M.E.1
-
Affiliations:
- Moscow Institute of Physics and Technology
- Issue: Vol 484, No 5 (2019)
- Pages: 519-522
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/12758
- DOI: https://doi.org/10.31857/S0869-56524845519-522
- ID: 12758
Cite item
Full Text
Abstract
We construct existential monadic second order sentences that have no limit probabilities on binomial sparse random graph G(n; n–α) . For α < , the constructions have only one monadic variable.
About the authors
A. N. Egorova
Moscow Institute of Physics and Technology
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, 9, Institutskij, Dolgoprudny, Moscow region, 141701
M. E. Zhukovskii
Moscow Institute of Physics and Technology
Email: zhukmax@gmail.com
Russian Federation, 9, Institutskij, Dolgoprudny, Moscow region, 141701
References
- Жуковский M.E., Райгородский А.М. // УМН. 2015. Т. 70. № 1. С. 35–88.
- Spencer J.H. The Strange Logic of Random Graphs. B.: Springer Verlag, 2001.
- Верещагин Н.К., Шень А. Языки и исчисления. М.: МНЦМО, 2000.
- Жуковский М.Е., Санчез М.Г. // ДАН. 2017. Т. 477. № 5. С. 513–515.
- Le Bars J.-M. // Inform. Processing Lett. 2001. V. 77. P. 43–48.
- Janson S., Luczak T., Rucinski A. Random Graphs. N.Y.: Wiley, 2000.
- Глебский Ю.В., Коган Д.И., Легонький М.И., Таланов В.А. // Кибернетика. 1969. Т. 2. С. 17–27.
- Fagin R. // J. Symbolic Logic. 1976. V. 41. P. 50–58.
- Жуковский М.Е., Медведева А.Е. // Мат. заметки. 2016. Т. 99. № 3. С. 342–349.
- Жуковский М.Е., Островский Л.Б. // Изв. РАН. Сер. мат. 2017. Т. 81. № 6. С. 100–113.
- Matushkin A.D., Zhukoυskii M.E. // Discrete Appl. Math. 2018. V. 236. P. 329–346.
- Kaufmann M., Shelah S. // Discrete Math. 1985. V. 54. P. 285–293.
- Kaufmann M. Counterexample to the 0-1 Law for Existential Monadic Second-Order Logic. Technical Report. CLI Internal Note 32. Computational Logic. December 1987.
- Shelah S., Spencer J.H. // J. Amer. Math. Soc. 1988. V. 1. P. 97–115.
- Tyszkiewicz J. // Lect. Notes in Comput. Sci. 1993. V. 702. P. 425–439.
Supplementary files
