Законы нуля или единицы для формул с k переменными

Обложка

Цитировать

Полный текст

Аннотация

Мы рассматриваем фрагмент логики первого порядка на графах, состоящий из предложений с k переменными. Мы утверждаем, что при α≤1κ-1 случайный граф G(n, n-α) подчиняется закону нуля или единицы для этого фрагмента. Более того, для каждого ε > 0 найдётся α∈1κ-1,1κ-1+ε, при котором случайный граф G(n, n-α) не подчиняется этому закону.

Об авторах

М. Е. Жуковский

Московский физико-технический институт (национальный исследовательский университет)

Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, 141701, Московская обл., г. Долгопрудный, Институтский пер., д.9

А. С. Разафимахатратра

Реджайнский университет или Университет Реджайны

Email: andriahermanana@aims.edu.gh
Канада, SK S4S 0A2, Реджайна, Васкана-Паркуэй 3737

Список литературы

  1. Libkin L. Elements of finite model theory. Texts in Theoretical Computer Science. An EATCS Series B.: Springer­Verlag, 2004.
  2. Zhukovskii M.E., Raigorodskii A.M. // Rus. Math. Surv. 2015. V. 70. № 1. P. 33-81.
  3. Burkin A.V., Zhukovskii M.E. In: Mathematics. 2018. V. 209. № 2. P. 163-186.
  4. Zhukovskii M.E., Ostrovskii L.B. // Izv. Math. 2017. V. 81. № 6. P. 1155-1167.
  5. Жуковский М.Е., Санчез М.Г. // ДАН. 2017. Т. 477. № 5. С. 513-515.
  6. Spencer J.H., Zhukovskii M.E. // Discrete Math. 2016. V. 339. № 6. P. 1651-1664.
  7. Fagin R. // J. Symbolic Logic. 1976. V. 41. P. 50-58.
  8. Glebskii Y.V., Kogan D.I., Liogon’kii M.I., Talanov V.A. // Cybernetics. 1969. V. 5. P. 142-154.
  9. Spencer J.H. // Discrete App. Math. 1991. V. 30. P. 235-252.
  10. Shelah S., Spencer J.H. // J. Amer. Math. Soc. 1988. V. 1. P. 97-115.
  11. Kolaitis P.G., Vardi M.Y. // Inform. and Comput. 1992. V. 98. P. 258-294.
  12. Lynch J.F. Proc. of the 8th IEEE Symp. on Logic in Computer Science. Cambridge, 1993. P. 191-198.
  13. McArthur M. // Logic and Random Structures. 1997. V. 33. P. 53-63.
  14. Spencer J.H. // Combinatorica. 1990. V. 10. № 1. P. 95-102.
  15. Zhukovskii M.E. // Moscow J. Combin. and Number Theory. 2016. V. 6. № 4. P. 73-102.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2019