First-order and monadic properties of highly sparse random graphs


Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

A random graph is said to obey the (monadic) zero–one k-law if, for any property expressed by a first-order formula (a second-order monadic formula) with a quantifier depth of at most k, the probability of the graph having this property tends to either zero or one. It is well known that the random graph G(n, n–α) obeys the (monadic) zero–one k-law for any k ∈ ℕ and any rational α > 1 other than 1 + 1/m (for any positive integer m). It is also well known that the random graph does not obey both k-laws for the other rational positive α and sufficiently large k. In this paper, we obtain lower and upper bounds on the largest at which both zero–one k-laws hold for α = 1 + 1/m.

Авторлар туралы

M. Zhukovskii

Moscow Institute of Physics and Technology (State University); RUDN University

Хат алмасуға жауапты Автор.
Email: zhukmax@gmail.com
Ресей, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 117198

L. Ostrovskii

Moscow Institute of Physics and Technology (State University)

Email: zhukmax@gmail.com
Ресей, Dolgoprudnyi, Moscow oblast, 141700

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML

© Pleiades Publishing, Ltd., 2016