RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Uspekhi Mat. Nauk:
Year:
Volume:
Issue:
Page:
Find






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


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
15-01-00350
Ministry of Education and Science of the Russian Federation -6277.2013.1
-2184.2014.1
-2519.2012.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.


DOI: https://doi.org/10.4213/rm9626

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
\Bibitem{ZhuRai15}
\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
\mathnet{http://mi.mathnet.ru/umn9626}
\crossref{https://doi.org/10.4213/rm9626}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3353116}
\zmath{https://zbmath.org/?q=an:06458416}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2015RuMaS..70...33Z}
\elib{http://elibrary.ru/item.asp?id=23421573}
\transl
\jour Russian Math. Surveys
\yr 2015
\vol 70
\issue 1
\pages 33--81
\crossref{https://doi.org/10.1070/RM2015v070n01ABEH004936}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000354181700002}
\elib{http://elibrary.ru/item.asp?id=24031809}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84929241453}


Linking options:
  • http://mi.mathnet.ru/eng/umn9626
  • https://doi.org/10.4213/rm9626
  • http://mi.mathnet.ru/eng/umn/v70/i1/p35

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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
    References:51
    First page:112

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