Zeroone laws for sentences with k variables
- Authors: Zhukovskii M.E.1, Razafimahatratra A.S.2
-
Affiliations:
- Moscow Institute of Physics and Technology
- University of Regina, Regina Saskatchewan
- Issue: Vol 486, No 2 (2019)
- Pages: 156-158
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/13404
- DOI: https://doi.org/10.31857/S0869-56524862156-158
- ID: 13404
Cite item
Full Text
Abstract
We consider the k variable fragment of first order logic on graphs. We claim that, for , the random graph G(n, n-α) obeys zeroone law w.r.t. this logic. Moreover, for every ε > 0 , there exists such that G(n, n-α) does not obey the law.
About the authors
M. E. Zhukovskii
Moscow Institute of Physics and Technology
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, 9, Institutskij, Dolgoprudny, Moscow region, 141701
A. S. Razafimahatratra
University of Regina, Regina Saskatchewan
Email: andriahermanana@aims.edu.gh
Canada, 3737 Wascana Pkwy, Regina, SK S4S 0A2
References
- Libkin L. Elements of finite model theory. Texts in Theoretical Computer Science. An EATCS Series B.: SpringerVerlag, 2004.
- Zhukovskii M.E., Raigorodskii A.M. // Rus. Math. Surv. 2015. V. 70. № 1. P. 33-81.
- Burkin A.V., Zhukovskii M.E. In: Mathematics. 2018. V. 209. № 2. P. 163-186.
- Zhukovskii M.E., Ostrovskii L.B. // Izv. Math. 2017. V. 81. № 6. P. 1155-1167.
- Жуковский М.Е., Санчез М.Г. // ДАН. 2017. Т. 477. № 5. С. 513-515.
- Spencer J.H., Zhukovskii M.E. // Discrete Math. 2016. V. 339. № 6. P. 1651-1664.
- Fagin R. // J. Symbolic Logic. 1976. V. 41. P. 50-58.
- Glebskii Y.V., Kogan D.I., Liogon’kii M.I., Talanov V.A. // Cybernetics. 1969. V. 5. P. 142-154.
- Spencer J.H. // Discrete App. Math. 1991. V. 30. P. 235-252.
- Shelah S., Spencer J.H. // J. Amer. Math. Soc. 1988. V. 1. P. 97-115.
- Kolaitis P.G., Vardi M.Y. // Inform. and Comput. 1992. V. 98. P. 258-294.
- Lynch J.F. Proc. of the 8th IEEE Symp. on Logic in Computer Science. Cambridge, 1993. P. 191-198.
- McArthur M. // Logic and Random Structures. 1997. V. 33. P. 53-63.
- Spencer J.H. // Combinatorica. 1990. V. 10. № 1. P. 95-102.
- Zhukovskii M.E. // Moscow J. Combin. and Number Theory. 2016. V. 6. № 4. P. 73-102.