Spectra of short monadic sentences about sparse random graphs

A random graph G(n, p) is said to obey the (monadic) zero–one k-law if, for any monadic formula of quantifier depth k, the probability that it is true for the random graph tends to either zero or one. In this paper, following J. Spencer and S. Shelah, we consider the case p = n−α. It is proved that the least k for which there are infinitely many α such that a random graph does not obey the zero–one k-law is equal to 4. © 2017, Pleiades Publishing, Ltd.

Авторы
Zhukovskii M.E. 1, 2 , Kupavskii A.B.1, 3
Журнал
Номер выпуска
1
Язык
Английский
Страницы
60-61
Статус
Опубликовано
Том
95
Год
2017
Организации
  • 1 Moscow Institute of Physics and Technology (State University), Dolgoprudnyi, Moscow oblast, 141700, Russian Federation
  • 2 RUDN University, Moscow, 117198, Russian Federation
  • 3 University Grenoble-Alpes, Grenoble, France
Дата создания
19.10.2018
Дата изменения
19.10.2018
Постоянная ссылка
https://repository.rudn.ru/ru/records/article/record/6030/
Поделиться

Другие записи