|
This article is cited in 4 scientific papers (total in 4 papers)
First-order properties of bounded quantifier depth of very sparse random graphs
M. E. Zhukovskiiab, L. B. Ostrovskiic a Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
b Peoples Friendship University of Russia, Moscow
c Company "Yandex"
Abstract:
We say that a random graph obeys the zero-one $k$-law if every property
expressed by a first-order formula with quantifier depth at most $k$
holds with probability tending to $0$ or $1$. It is known that the
random graph $G(n,n^{-\alpha})$ obeys the zero-one $k$-law for every
$k\in\mathbb{N}$ and every positive irrational $\alpha$, as well as for all
rational $\alpha>1$ which are not of the form $1+1/l$ (for any positive
integer $l$). It is also known that for all other rational positive $\alpha$,
the random graph does not obey the zero-one $k$-law for sufficiently large $k$.
In this paper we put $\alpha=1+1/l$ and obtain upper and lower bounds for
the largest $k$ such that the zero-one $k$-law holds.
Keywords:
Erdős–Rényi random graph, first-order properties, zero-one law, Ehrenfeucht game.
Received: 29.03.2016 Revised: 30.10.2016
Citation:
M. E. Zhukovskii, L. B. Ostrovskii, “First-order properties of bounded quantifier depth of very sparse random graphs”, Izv. RAN. Ser. Mat., 81:6 (2017), 100–113; Izv. Math., 81:6 (2017), 1155–1167
Linking options:
https://www.mathnet.ru/eng/im8557https://doi.org/10.1070/IM8557 https://www.mathnet.ru/eng/im/v81/i6/p100
|
Statistics & downloads: |
Abstract page: | 440 | Russian version PDF: | 54 | English version PDF: | 15 | References: | 49 | First page: | 22 |
|