RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2020 Volume 211, Number 7, Pages 60–71 (Mi sm9321)

This article is cited in 2 papers

First-order zero-one law for the uniform model of the random graph

M. E. Zhukovskiiab, N. M. Sveshnikovc

a Advanced Combinatorics and Networking Lab, Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region
b Moscow Center for Fundamental and Applied Mathematics
c Phystech School of Applied Mathematics and Informatics, Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region

Abstract: The paper considers the Erdős-Rényi random graph in the uniform model $G(n,m)$, where $m=m(n)$ is a sequence of nonnegative integers such that $m(n)\sim cn^{\alpha}<(2-\varepsilon)n^2$ for some $c>0$, $\alpha\in[0,2]$, and $\varepsilon>0$. It is shown that $G(n,m)$ obeys the zero-one law for the first-order language if and only if either $\alpha\in\{0,2\}$, or $\alpha$ is irrational, or $\alpha\in(0,1)$ and $\alpha$ is not a number of the form $1-1/\ell$, $\ell\in\mathbb{N}$.
Bibliography: 15 titles.

Keywords: zero-one law, first-order logic, uniform model of the random graph.

UDC: 519.179.4

MSC: Primary 05C80, 60F20; Secondary 03C07

Received: 21.08.2019 and 28.01.2020

DOI: 10.4213/sm9321


 English version:
Sbornik: Mathematics, 2020, 211:7, 956–966

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024