|
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)∼cnα<(2−ε)n2 for some c>0, α∈[0,2], and ε>0. It is shown that G(n,m) obeys the zero-one law for the first-order language if and only if either α∈{0,2}, or α is irrational, or α∈(0,1) and α is not a number of the form 1−1/ℓ, ℓ∈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
|
Statistics & downloads: |
Abstract page: | 372 | Russian version PDF: | 69 | English version PDF: | 46 | References: | 40 | First page: | 17 |
|