Random graphs: models and asymptotic characteristics

M. E. Zhukovskii   ; A. M. Raigorodskii

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 70 (2015) no. 1, pp. 33-81

Résumé

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.

Détail

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

Bibliographie

[1] V. L. Goncharov, “O raspredelenii tsiklov v perestanovkakh”, Dokl. AN SSSR, 35:9 (1942), 299–301 | Zbl

[2] T. Szele, “Kombinatorikai vizsgálatok az irányitott teljes gráffal kapcsolatban”, Mat. Fiz. Lapok, 50 (1943), 223–256 | MR | Zbl

[3] P. Erdős, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38 | DOI | MR | Zbl

[4] P. Erdős, A. Rényi, “On random graphs. I”, Publ. Math. Debrecen, 6 (1959), 290–297 | MR | Zbl

[5] P. Erdős, A. Rényi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17–61 | MR | Zbl

[6] P. Erdős, A. Rényi, “On the evolution of random graphs”, Bull. Inst. Internat. Statist., 38 (1961), 343–347 | MR | Zbl

[7] V. F. Kolchin, Sluchainye grafy, 2-e izd., Fizmatlit, M., 2004, 256 pp. ; V. F. Kolchin, Random graphs, Encyclopedia Math. Appl., 53, Cambridge Univ. Press, Cambridge, 1999, xii+252 pp. | MR | Zbl | MR | Zbl

[8] N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 3rd ed., John Wiley Sons, Inc., Hoboken, NJ, 2008, xviii+352 pp. | DOI | MR | Zbl

[9] B. Bollobás, Random graphs, Cambridge Stud. Adv. Math., 73, 2nd ed., Cambridge Univ. Press, Cambridge, 2001, xviii+498 pp. | DOI | MR | Zbl

[10] S. Janson, T. Łuczak, A. Ruciński, Random graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000, xii+333 pp. | DOI | MR | Zbl

[11] A. M. Raigorodskii, Modeli sluchainykh grafov, MTsNMO, M., 2011, 136 pp.

[12] A. M. Raigorodskii, Modeli interneta, Intellekt, Dolgoprudnyi, 2013, 64 pp.

[13] L. Lovász, Large networks and graph limits, Amer. Math. Soc. Colloq. Publ., 60, Amer. Math. Soc., Providence, RI, 2012, xiv+475 pp. | MR | Zbl

[14] S. N. Dorogovtsev, Lectures on complex networks, Oxf. Master Ser. Phys., 20, Oxford Univ. Press, Oxford, 2010, x+134 pp. | DOI | MR | Zbl

[15] M. Penrose, Random geometric graphs, Oxford Stud. Probab., 5, Oxford Univ. Press, Oxford, 2003, xiv+330 pp. | DOI | MR | Zbl

[16] M. E. J. Newman, Networks. An introduction, Oxford Univ. Press, Oxford, 2010, xii+772 pp. | DOI | MR | Zbl

[17] B. Bollobás, A. Thomason, “Threshold functions”, Combinatorica, 7:1 (1987), 35–38 | DOI | MR | Zbl

[18] A. Ruciński, A. Vince, “Balanced graphs and the problem of subgraphs of a random graph”, Proceedings of the Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1985), Congr. Numer., 49 (1985), 181–190 | MR | Zbl

[19] B. Bollobás, “Threshold functions for small subgraphs”, Math. Proc. Cambridge Philos. Soc., 90:2 (1981), 197–206 | DOI | MR | Zbl

[20] A. Ruciński, A. Vince, “Strongly balanced graphs and random graphs”, J. Graph Theory, 10:2 (1986), 251–264 | DOI | MR | Zbl

[21] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007, 138 pp. | Zbl

[22] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1(337) (2001), 107–146 | DOI | MR | Zbl

[23] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty essays on geometric graph theory, ed. J. Pach, Springer, New York, 2013, 429–460 | DOI | MR | Zbl

[24] J. Pach, P. K. Agarwal, Combinatorial geometry, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley Sons, Inc., New York, 1995, xiv+354 pp. | DOI | MR | Zbl

[25] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics (Budapest, 1999), v. II, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., 2002, 649–666 | MR | Zbl

[26] A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Springer, New York, 2009, xxx+607 pp. | DOI | MR | Zbl

[27] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Dolciani Math. Exp., 11, Math. Assoc. America, Washington, DC, 1991, xvi+333 pp. | MR | Zbl

[28] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete geometry and algebraic combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | DOI | Zbl

[29] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

[30] J. Kahn, G. Kalai, “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc. (N. S.), 29:1 (1993), 60–62 | DOI | MR | Zbl

[31] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, New York, 2005, xii+499 pp. | DOI | MR | Zbl

[32] F. Dzh. Mak-Vilyams, N. Dzh. A. Sloen, Teoriya kodov, ispravlyayuschikh oshibki, Svyaz, M., 1979, 744 pp. ; F. J. MacWilliams, N. J. A. Sloane, The theory of error-correcting codes. Parts I, II, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam–New York–Oxford, 1977, xv+ix+762 pp. | Zbl | MR | MR | Zbl

[33] V. Rödl, “On a packing and covering problem”, European J. Combin., 6:1 (1985), 69–78 | DOI | MR | Zbl

[34] L. Bassalygo, G. Cohen, G. Zémor, “Codes with forbidden distances”, Selected topics in discrete mathematics (Warsaw, 1996), Discrete Math., 213:1-3 (2000), 3–11 | DOI | MR | Zbl

[35] M. E. Zhukovskii, “O posledovatelnosti sluchainykh distantsionnykh grafov, podchinyayuscheisya zakonu nulya ili edinitsy”, Probl. peredachi inform., 47:3 (2011), 39–57 | MR | Zbl

[36] M. E. Zhukovskii, “Oslablennyi zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov”, Teoriya veroyatn. i ee primen., 55:2 (2010), 344–349 ; M. E. Zhukovskii, “The weak zero-one law for the random distance graphs”, Theory Probab. Appl., 55:2 (2011), 356–360 | DOI | MR | Zbl | DOI

[37] M. E. Zhukovskii, “Oslablennyi zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov”, Dokl. RAN, 430:3 (2010), 314–317 | MR | Zbl

[38] M. E. Zhukovskii, “Oslablennyi zakon nulya ili edinitsy dlya posledovatelnostei sluchainykh distantsionnykh grafov”, Matem. sb., 203:7 (2012), 95–128 | DOI | MR | Zbl

[39] M. E. Zhukovskii, “Oslablennyi zakon ‘nulya ili edinitsy’ dlya sluchainykh distantsionnykh grafov”, Vestn. RUDN, 2:1 (2010), 11–25

[40] S. N. Popova, “Zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Probl. peredachi inform., 50:1 (2014), 64–86 | MR

[41] M. E. Zhukovskii, “O veroyatnosti vkhozhdeniya kopii fiksirovannogo grafa v sluchainyi distantsionnyi graf”, Matem. zametki, 92:6 (2012), 844–855 | DOI | MR | Zbl

[42] L. I. Bogolyubskii, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Chisla nezavisimosti i khromaticheskie chisla sluchainykh podgrafov v nekotorykh posledovatelnostyakh grafov”, Dokl. RAN, 457:4 (2014), 383–387 | DOI

[43] L. I. Bogolubsky, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Independence numbers and chromatic numbers of the random subgraphs of some distance graphs”, Sb. Math., 206:10 (2015), 1340–1374 | DOI | DOI | MR | Zbl

[44] A. B. Kupavskii, “On random subgraphs of Kneser graph”, J. Combin. Theory Ser. A (to appear)

[45] B. Bollobás, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős–Ko–Rado theorem”, J. Combin. Theory Ser. A (to appear)

[46] N. K. Vereschagin, A. Shen, Yazyki i ischisleniya, MTsNMO, M., 2000, 286 pp.

[47] V. A. Uspenskii, N. K. Vereschagin, V. E. Plisko, Vvodnyi kurs matematicheskoi logiki, Fizmatlit, M., 2007, 128 pp. | Zbl

[48] A. Ehrenfeucht, “An application of games to the completness problem for formalized theories”, Fund. Math., 49 (1960/1961), 121–141 | MR | Zbl

[49] J. Spencer, The strange logic of random graphs, Algorithms Combin., 22, Springer-Verlag, Berlin, 2001, x+168 pp. | DOI | MR | Zbl

[50] S. Shelah, J. Spencer, “Zero-one laws for sparse random graphs”, J. Amer. Math. Soc., 1:1 (1988), 97–115 | DOI | MR | Zbl

[51] Yu. V. Glebskii, D. I. Kogan, M. I. Liogonkii, V. A. Talanov, “Ob'em i dolya vypolnimosti formul uzkogo ischisleniya predikatov”, Kibernetika, 2 (1969), 17–27 | MR | Zbl

[52] R. Fagin, “Probabilities in finite models”, J. Symbolic Logic, 41:1 (1976), 50–58 | DOI | MR | Zbl

[53] B. Kreuter, “Threshold functions for asymmetric Ramsey properties with repect to vertex colorings”, Random Structures Algorithms, 9:3 (1996), 335–348 | 3.0.CO;2-Y class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[54] J. Spencer, “Counting extensions”, J. Combin. Theory Ser. A, 55:2 (1990), 247–255 | DOI | MR | Zbl

[55] T. Łuczak, J. Spencer, “When does the zero-one law hold?”, J. Amer. Math. Soc., 4:3 (1991), 451–468 | DOI | MR | Zbl

[56] J. F. Lynch, “Probabilities of sentences about very sparse random graphs”, Random Structures Algorithms, 3:1 (1992), 33–53 | DOI | MR | Zbl

[57] M. McArthur, “The asymptotic behavior of $L^k_{\infty,\omega}$ on sparse random graphs”, Logic and random structures (New Brunswick, NJ, 1995), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 33, Amer. Math. Soc., Providence, RI, 1997, 53–63 | MR | Zbl

[58] Ph. G. Kolaitis, H. J. Prömel, B. L. Rothschild, “$K_{l+1}$-free graphs: asymptotic structure and a $0$-$1$ law”, Trans. Amer. Math. Soc., 303:2 (1987), 637–671 | DOI | MR | Zbl

[59] R. H. Gilman, Y. Gurevich, A. Miasnikov, “A geometric zero-one law”, 2007, 13 pp., arXiv: 0706.0271

[60] M. Zhukovskii, “Zero-one $k$-law”, Discrete Math., 312:10 (2012), 1670–1688 | DOI | MR | Zbl

[61] M. E. Zhukovskii, “Otsenka kolichestva maksimalnykh rasshirenii v sluchainom grafe”, Diskret. matem., 24:1 (2012), 79–107 | DOI | MR | Zbl

[62] M. E. Zhukovskii, “Rasshirenie $k$-zakona nulya ili edinitsy”, Dokl. RAN, 454:1 (2014), 23–26 | DOI | MR | Zbl

[63] M. E. Zhukovskii, “The largest critical point in the zero-one $k$-law”, Sb. Math., 206:4 (2015), 489–509 | DOI | DOI | MR | Zbl

[64] J. Spencer, “Infinite spectra in the first order theory of graphs”, Combinatorica, 10:1 (1990), 95–102 | DOI | MR | Zbl

[65] S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in $\mathbb Z^n$”, Sb. Math., 207:3 (2016), 458–478 | DOI | DOI | MR