Sbornik: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sbornik: Mathematics, 2020, Volume 211, Issue 7, Pages 956–966
DOI: https://doi.org/10.1070/SM9321
(Mi sm9321)
 

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
References:
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.
Funding agency Grant number
Russian Science Foundation 18-71-00069
The research of M. E. Zhukovskii was supported by the Russian Science Foundation (project no. 18-71-00069) in the Advanced Combinatorics and Networking Lab of the Moscow Institute of Physics and Technology (National Research University). Sections 2.2, 2.3 and 2.5, as well as the proofs of Theorems 4 and 6, were written by M. E. Zhukovskii. Sections 1, 2.1 and 2.4, as well as the proof of Theorem 5, were written by N. M. Sveshnikov.
Received: 21.08.2019 and 28.01.2020
Russian version:
Matematicheskii Sbornik, 2020, Volume 211, Number 7, Pages 60–71
DOI: https://doi.org/10.4213/sm9321
Bibliographic databases:
Document Type: Article
UDC: 519.179.4
MSC: Primary 05C80, 60F20; Secondary 03C07
Language: English
Original paper language: Russian
Citation: M. E. Zhukovskii, N. M. Sveshnikov, “First-order zero-one law for the uniform model of the random graph”, Mat. Sb., 211:7 (2020), 60–71; Sb. Math., 211:7 (2020), 956–966
Citation in format AMSBIB
\Bibitem{ZhuSve20}
\by M.~E.~Zhukovskii, N.~M.~Sveshnikov
\paper First-order zero-one law for~the~uniform~model of the random graph
\jour Mat. Sb.
\yr 2020
\vol 211
\issue 7
\pages 60--71
\mathnet{http://mi.mathnet.ru/sm9321}
\crossref{https://doi.org/10.4213/sm9321}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4045698}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2020SbMat.211..956Z}
\elib{https://elibrary.ru/item.asp?id=45283034}
\transl
\jour Sb. Math.
\yr 2020
\vol 211
\issue 7
\pages 956--966
\crossref{https://doi.org/10.1070/SM9321}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000573486400001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85092051086}
Linking options:
  • https://www.mathnet.ru/eng/sm9321
  • https://doi.org/10.1070/SM9321
  • https://www.mathnet.ru/eng/sm/v211/i7/p60
  • This publication is cited in the following 2 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Statistics & downloads:
    Abstract page:326
    Russian version PDF:57
    English version PDF:30
    References:33
    First page:17
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024