Loading [MathJax]/jax/output/CommonHTML/jax.js
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)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 11/, 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
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”, 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 Sb. Math.
\yr 2020
\vol 211
\issue 7
\pages 956--966
\mathnet{http://mi.mathnet.ru/eng/sm9321}
\crossref{https://doi.org/10.1070/SM9321}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4045698}
\zmath{https://zbmath.org/?q=an:1448.05184}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2020SbMat.211..956Z}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000573486400001}
\elib{https://elibrary.ru/item.asp?id=45283034}
\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:
    1. Danila Demin, Maksim Zhukovskii, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024, 1  crossref
    2. Y. A. Malyshkin, M. E. Zhukovskii, “Mso 0-1 law for recursive random trees”, Stat. Probab. Lett., 173 (2021), 109061  crossref  mathscinet  isi  scopus
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Statistics & downloads:
    Abstract page:372
    Russian version PDF:69
    English version PDF:46
    References:40
    First page:17
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025