No Access

Logical laws for short existential monadic second-order sentences about graphs

M. E. Zhukovskii

Moscow Institute of Physics and Technology (National Research University), Laboratory of Advanced Combinatorics and Network Applications, 9 Institutskiy per., Dolgoprodny, Moscow Region 141701, Russian Federation

Adyghe State University, Caucasus Mathematical Center, ul. Pervomayskaya, 208, Maykop, Republic of Adygea, 385000, Russian Federation

The Russian Presidential Academy of National Economy and Public Administration, Prospect Vernadskogo, 84, bldg 2, Moscow 119571, Russian Federation

E-mail Address: zhukmax@gmail.com

Search for more papers by this author

https://doi.org/10.1142/S0219061320500075Cited by:2 (Source: Crossref)

Abstract

In 2001, Le Bars proved that there exists an existential monadic second-order (EMSO) sentence such that the probability that it is true on $G (n, p = 1 / 2)$ $G (n, p = 1 / 2)$ does not converge and conjectured that, for EMSO sentences with two first-order variables, the zero–one law holds. In this paper, we prove that the conjecture fails for $p \in {\frac{3 - \sqrt{5}}{2}, \frac{\sqrt{5} - 1}{2}}$ $p \in {\frac{3 - \sqrt{5}}{2}, \frac{\sqrt{5} - 1}{2}}$ , and give new examples of sentences with fewer variables without convergence (even for $p = 1 / 2$ $p = 1 / 2$ ).

Keywords:

AMSC: 03B15, 03C13, 05C80

References

1. N. Alon and J. H. Spencer, The Probabilistic Method (John Wiley & Sons, 2000). Crossref, Google Scholar
2. J. Barwise, Handbook of Mathematical Logic (Elsevier Science Publishers B.V., 1977). Google Scholar
3. B. Bollobás, Random Graphs, 2nd edn. (Cambridge University Press, 2001). Crossref, Google Scholar
4. K. J. Compton, A logical approach to asymptotic combinatorics. II. Monadic second-order properties, J. Comb. Th., Ser. A 50(1) (1989) 110–131. Crossref, Web of Science, Google Scholar
5. H.-D. Ebbinghaus and J. Flum, Finite Model Theory, Perspectives in Mathematical Logic, 2nd edn. (Springer-Verlag, Berlin, 1999). Crossref, Google Scholar
6. A. Ehrenfeucht, An application of games to the completness problem for formalized theories, Warszawa, Fund. Math. 49 (1960) 121–149. Google Scholar
7. P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960) 17–61. Google Scholar
8. R. Fagin, Probabilities in finite models, J. Symbolic Logic 41 (1976) 50–58. Crossref, Web of Science, Google Scholar
9. Y. V. Glebskii, D. I. Kogan, M. I. Liogon’kii and V. A. Talanov, Range and degree of realizability of formulas the restricted predicate calculus, Cybernetics 5 (1969) 142–154 (Russian original: Kibernetica 2, 17–27). Crossref, Google Scholar
10. P. Heinig, T. Müller, M. Noy and A. Taraz, Logical limit laws for minor-closed classes of graphs, to appear in J. Comb. Th. Ser. B., submitted in 2014, arXiv:1401.7021. Google Scholar
11. S. Janson, T. Luczak and A. Rucinski, Random Graphs (Wiley, New York, 2000). Crossref, Google Scholar
12. M. Kaufmann, Counterexample to the 0-1 law for existential monadic second-order logic, Technical report, CLI Internal Note 32, Computational Logic Inc., December (1987). Google Scholar
13. M. Kaufmann and S. Shelah, On random models of finite power and monadic logic, Discrete Math. 54 (1985) 285–293. Crossref, Web of Science, Google Scholar
14. J.-M. Le Bars, The 0-1 law fails for monadic existential second-order logic on undirected graphs, Inf. Process. Lett. 77 (2001) 43–48. Crossref, Web of Science, Google Scholar
15. L. Libkin, Elements of Finite Model Theory, Texts in Theoretical Computer Science, An EATCS Series (Springer-Verlag, Berlin, Heidelberg, 2004). Crossref, Google Scholar
16. J. F. Lynch, Almost sure theories, Annal. Math. Logic 18 (1980) 91–135. Crossref, Google Scholar
17. A. D. Matushkin and M. E. Zhukovskii, First order sentences about random graphs: Small number of alternations, to appear in Discrete Appl. Math., submitted in 2017, arXiv:1701.06517v3. Google Scholar
18. L. B. Ostrovsky and M. E. Zhukovskii, Monadic second-order properties of very sparse random graphs, Annal. Pure Appl. Logic 168(11) (2017) 2087–2101. Crossref, Web of Science, Google Scholar
19. J. H. Spencer, Threshold spectra via the Ehrenfeucht game, Discrete Appl. Math. 30 (1991) 235–252. Crossref, Web of Science, Google Scholar
20. J. H. Spencer, The Strange Logic of Random Graphs (Springer-Verlag, 2001). Crossref, Google Scholar
21. N. K. Vereshagin and A. Shen, Languages and Calculus (MCCME, Moscow, 2012). Google Scholar
22. M. E. Zhukovskii and A. M. Raigorodskii, Random graphs: Models and asymptotic characteristics, Russian Math. Surv. 70(1) (2015) 33–81. Crossref, Web of Science, Google Scholar