General information
Latest issue
Impact factor
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Uspekhi Mat. Nauk:

Personal entry:
Save password
Forgotten password?

Uspekhi Mat. Nauk, 2015, Volume 70, Issue 1(421), Pages 35–88 (Mi umn9626)  

This article is cited in 21 scientific papers (total in 21 papers)

Random graphs: models and asymptotic characteristics

M. E. Zhukovskiia, A. M. Raigorodskiiab

a Moscow Institute of Physics and Technology (State University)
b Moscow State University

Abstract: This is a survey of known results related to the asymptotic behaviour of the probabilities of first-order properties of random graphs. The results presented in this paper are concerned with zero-one laws for properties of random graphs. Emphasis is placed on the Erdős–Rényi model of a random graph. Also considered are some generalizations of this model motivated by various problems in the theory of coding and combinatorial geometry.
Bibliography: 65 titles.

Keywords: random graphs, distance graphs, limit theorems, zero-one laws, first-order properties.

Funding Agency Grant Number
Russian Foundation for Basic Research 13-01-00612
Ministry of Education and Science of the Russian Federation -6277.2013.1
This work was supported by the Russian Foundation for Basic Research (projects nos. 13-01-00612 and 15-01-00350) and by the Council of the President of the Russian Federation for the Support of Young Russian Scientists and Leading Scientific Schools, grants -6277.2013.1, MK-2184.2014.1, and -2519.2012.1.


Full text: PDF file (901 kB)
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 2015, 70:1, 33–81

Bibliographic databases:

UDC: 519.175.4
MSC: Primary 05C80, 60F20; Secondary 03C07
Received: 05.09.2014

Citation: M. E. Zhukovskii, A. M. Raigorodskii, “Random graphs: models and asymptotic characteristics”, Uspekhi Mat. Nauk, 70:1(421) (2015), 35–88; Russian Math. Surveys, 70:1 (2015), 33–81

Citation in format AMSBIB
\by M.~E.~Zhukovskii, A.~M.~Raigorodskii
\paper Random graphs: models and asymptotic characteristics
\jour Uspekhi Mat. Nauk
\yr 2015
\vol 70
\issue 1(421)
\pages 35--88
\jour Russian Math. Surveys
\yr 2015
\vol 70
\issue 1
\pages 33--81

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. M. E. Zhukovskii, “The spectra of first-order formulae having low quantifier rank”, Russian Math. Surveys, 70:6 (2015), 1176–1178  mathnet  crossref  crossref  mathscinet  zmath  isi  elib
    2. M. E. Zhukovskii, “On limit points of spectra of the random graph first-order properties”, Dokl. Math., 92:3 (2015), 719–722  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    3. M. E. Zhukovskii, A. Medvedeva, “When Does the Zero-One $k$-Law Fail?”, Math. Notes, 99:3 (2016), 362–367  mathnet  crossref  crossref  mathscinet  isi  elib
    4. M. E. Zhukovskii, A. D. Matushkin, “Universal Zero-One $k$-Law”, Math. Notes, 99:4 (2016), 511–523  mathnet  crossref  crossref  mathscinet  isi  elib
    5. J. H. Spencer, M. E. Zhukovskii, “Bounded quantifier depth spectra for random graphs”, Discrete Math., 339:6 (2016), 1651–1664  crossref  mathscinet  zmath  isi  elib  scopus
    6. M. E. Zhukovskii, L. B. Ostrovskii, “First-order and monadic properties of highly sparse random graphs”, Dokl. Math., 94:2 (2016), 555–557  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    7. M. E. Zhukovskii, L. B. Ostrovskii, “First-order properties of bounded quantifier depth of very sparse random graphs”, Izv. Math., 81:6 (2017), 1155–1167  mathnet  crossref  crossref  adsnasa  isi  elib
    8. M. E. Zhukovskii, M. G. Sánchez, “Logical laws for existential monadic second-order sentences with infinite first-order parts”, Dokl. Math., 96:3 (2017), 598–600  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    9. L. B. Ostrovsky, M. E. Zhukovskii, “Monadic second-order properties of very sparse random graphs”, Ann. Pure Appl. Logic, 168:11 (2017), 2087–2101  crossref  mathscinet  zmath  isi  scopus
    10. M. E. Zhukovskii, A. D. Matushkin, “Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations”, Dokl. Math., 96:1 (2017), 326–328  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    11. M. E. Zhukovskii, “On first-order definitions of subgraph isomorphism properties”, Dokl. Math., 96:2 (2017), 454–456  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    12. M. E. Zhukovskii, A. B. Kupavskii, “Spectra of Short Monadic Sentences About Sparse Random Graphs”, Dokl. Math., 95:1 (2017), 60–61  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    13. M. E. Zhukovskii, “Quantifier alternation in first-order formulas with infinite spectra”, Problems Inform. Transmission, 53:4 (2017), 391–403  mathnet  crossref  isi  elib
    14. A. V. Burkin, M. E. Zhukovskii, “Small subgraphs and their extensions in a random distance graph”, Sb. Math., 209:2 (2018), 163–186  mathnet  crossref  crossref  adsnasa  isi  elib
    15. A. D. Matushkin, M. E. Zhukovskii, “First order sentences about random graphs: small number of alternations”, Discrete Appl. Math., 236 (2018), 329–346  crossref  mathscinet  zmath  isi  scopus
    16. S. N. Popova, “Infinite spectra of first-order properties for random hypergraphs”, Problems Inform. Transmission, 54:3 (2018), 281–289  mathnet  crossref  isi
    17. M. E. Zhukovskii, I. V. Rodionov, “On the distribution of the maximum k-degrees of the binomial random graph”, Dokl. Math., 98:3 (2018), 619–621  crossref  crossref  zmath  isi  elib
    18. M. E. Zhukovskii, S. N. Popova, “A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences”, Dokl. Math., 98:3 (2018), 638–640  mathnet  crossref  crossref  zmath  isi  elib
    19. Kupavskii A., Zhukovskii M., “Short Monadic Second Order Sentences About Sparse Random Graphs”, SIAM Discret. Math., 32:4 (2018), 2916–2940  crossref  isi
    20. Popova S.N., Zhukovskii M.E., “Existential Monadic Second Order Logic of Undirected Graphs: the Le Bars Conjecture Is False”, Ann. Pure Appl. Log., 170:4 (2019), 505–514  crossref  mathscinet  zmath  isi  scopus
    21. Egorova A.N., Zhukovskii M.E., “Disproof of the Zero-One Law For Existential Monadic Properties of a Sparse Binomial Random Graph”, Dokl. Math., 99:1 (2019), 68–70  crossref  isi
  •   Russian Mathematical Surveys
    Number of views:
    This page:889
    Full text:257
    First page:112

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020