RUS  ENG
Full version
JOURNALS // Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya // Archive

Izv. RAN. Ser. Mat., 2017 Volume 81, Issue 6, Pages 100–113 (Mi im8557)

This article is cited 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.

UDC: 519.175.4

MSC: 03B10, 03C13, 05C80, 60F20

Received: 29.03.2016
Revised: 30.10.2016

DOI: 10.4213/im8557


 English version:
Izvestiya: Mathematics, 2017, 81:6, 1155–1167

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024