|
This article is cited in 2 scientific papers (total 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.
Received: 21.08.2019 and 28.01.2020
Citation:
M. E. Zhukovskii, N. M. Sveshnikov, “First-order zero-one law for the uniform model of the random graph”, Sb. Math., 211:7 (2020), 956–966
Linking options:
https://www.mathnet.ru/eng/sm9321https://doi.org/10.1070/SM9321 https://www.mathnet.ru/eng/sm/v211/i7/p60
|
|