Janson, Svante; Knuth, Donald E.; Łuczak, Tomasz; Pittel, Boris The birth of the giant component. (English) Zbl 0795.05127 Random Struct. Algorithms 4, No. 3, 233-358 (1993). A unified approach to graph evolution is presented based on the notions of excess and deficiency. The asymptotic structure of a Markov process is derived which describes how the components grow in cyclic complexity. Reviewer: O.Frank (Stockholm) Cited in 4 ReviewsCited in 95 Documents MSC: 05C80 Random graphs (graph-theoretic aspects) 60J99 Markov processes Keywords:giant component; random graph; graph evolution; excess; deficiency; Markov process; cyclic complexity PDFBibTeX XMLCite \textit{S. Janson} et al., Random Struct. Algorithms 4, No. 3, 233--358 (1993; Zbl 0795.05127) Full Text: DOI arXiv Digital Library of Mathematical Functions: §16.23(ii) Random Graphs ‣ §16.23 Mathematical Applications ‣ Applications ‣ Chapter 16 Generalized Hypergeometric Functions and Meijer 𝐺-Function §9.13(ii) Generalizations from Integral Representations ‣ §9.13 Generalized Airy Functions ‣ Related Functions ‣ Chapter 9 Airy and Related Functions Online Encyclopedia of Integer Sequences: Number of trees on n labeled nodes: n^(n-2) with a(0)=1. Number of connected labeled graphs with n nodes and n+5 edges. Number of connected labeled graphs with n nodes and n+7 edges. Number of connected labeled graphs with n nodes and n+8 edges. Number of connected graphs on n unlabeled nodes that contain at least two cycles. Number of unlabeled graphs of positive excess with n nodes. Number of connected labeled graphs with n nodes and n+9 edges. Number of connected labeled graphs with n nodes and n+10 edges. Number of connected labeled graphs with n nodes and n+11 edges. References: [1] Bagaev, Diskretny?? Analiz 22 pp 3– (1973) [2] Bagaev, Dokl. Akad. Nauk. BSSR 28 pp 1061– (1984) [3] Bender, Random Struct. Alg. 1 pp 127– (1990) [4] Bollobás, Eur. J. Combinatorics 1 pp 311– (1980) · Zbl 0457.05038 [5] Bollobás, Trans. Am. Math. Soc. 286 pp 257– (1984) [6] Random Graphs, Academic Press, London, 1985. [7] and , On matchings and Hamiltonian cycles in random graphs, in Random Graphs ’83 ( and , Eds.), Ann. Discrete Math., 28, 23–46 (1985). [8] Borchardt, J. reine angewandte Math. 57 pp 111– (1860) [9] Britikov, Diskretnaia Matematika 1 pp 121– (1989) [10] Discrete Math. Appl. 1 pp 301– (1991) [11] Cayley, Q. J. Pure Appl. Math. 23 pp 376– (1889) [12] Math. Papers 13 pp 26– [13] Eisenstein, J. reine angewandte Math. 28 pp 49– (1844) [14] Erdõs, Publ. Math., (Debrecen) 6 pp 290– (1959) [15] Reprinted in The Art of Counting, MIT Press, Cambridge, MA, 1973, pp. 561–568; [16] and in Selected Papers of Alfréd Rényi, Akadémiai Kiadó, 1976, pp. 308–315. [17] Erdõs, Magy. Tud. Akad. Mat. Kut. Intéz. Közl. 5 pp 17– (1960) [18] Reprinted in The Art of Counting, MIT Press, Cambridge, MA, 1973, pp. 574–618; and [19] in Seclected Papers of Alfréd Rényi, Akadémiai Kiadó, 1976, pp. 482–525. [20] Flajolet, Discrete Math. 75 pp 167– (1989) [21] Fortuin, Commun. Math. Phys. 22 pp 89– (1971) [22] and , Combinatorial Enumeration, Wiley, New York, 1983. [23] , and , Concrete Mathematics, Addison-Wesley, Reading, MA, 1989. [24] Applied and Computational Complex Analysis, volume 2, Wiley, New York, 1977. [25] Janson, Random Struct. Alg. 4 pp 71– (1993) [26] Janson, Abstr. Am. Math. Soc. 13 pp 354– (1992) [27] Karp, Random Struct. Alg. 1 pp 73– (1990) [28] Knuth, J. Algorithms 6 pp 181– (1985) [29] Knuth, Mathematica J. 2 pp 67– (1992) [30] Knuth, Proc. Am. Math. Soc. 105 pp 335– (1989) [31] Łuczak, Random Stuct. Alg. 1 pp 287– (1990) [32] Łuczak, Random Struct. Alg. 2 pp 421– (1991) · Zbl 0755.05089 [33] Łuczak, Combinatorica 9 pp 39– (1989) [34] Łuczak, Trans. Am. Math. Soc. [35] Analytic Inequalities, Springer-Verlag, New York, 1970. · Zbl 0199.38101 [36] Ramanujan, J. Indian Math. Soc. 3 pp 128– (1911) [37] J. Indian Math. Soc. 4 pp 151– (1912) [38] Rényi, Magy. Tud. Akad. Mat. Kut. Intéz. Közl. 4 pp 73– (1959) [39] Selected Papers of Alfréd Rényi 2 pp 363– [40] Contributions to the Theory of Condensation, Dissertation, University of Michigan, 1951. [41] Riddell, J. Chem. Phys. 21 pp 2056– (1953) [42] Seitz, Aktuarské Vědy 6 pp 167– (1936/37) [43] Slater, Proc. Cambridge Philos. Soc. 50 pp 628– (1954) [44] ”Nelskol’ko teorem otnositel’no slucha??nykh grafov,” Veroiatnostnye metody v diskretno?? matematike (Karel’ski?? filial Akad. Nauk SSSR, Petrozavodsk, 1983), pp. 90–92. [45] Stepanov, Teor. Veroyatn. Ee Primen. 32 pp 633– (1988) [46] Theory Probab. Its Appl. 32 pp 573– (1988) · Zbl 0656.60021 [47] Sylvester, Q. J. Pure Appl. Math. 1 pp 42– (1857) [48] Math. Papers 2 pp 65– [49] Vobly??, Mat. Zametki 42 pp 854– (1987) [50] Voblyi, Math. Notes 42 pp 969– (1987) · Zbl 0698.05037 [51] Wright, Proc. London Math. Soc. 17 pp 296– (1967) [52] Wright, Bull. London Math. Soc. 3 pp 348– (1971) [53] Wright, J. Graph Theory 1 pp 317– (1977) [54] Wright, Q. J. Math. 28 pp 363– (1977) [55] Wright, J. Graph Theory 2 pp 299– (1978) [56] Wright, J. Graph Theory 4 pp 393– (1980) [57] Wright, J. Graph Theory 7 pp 219– (1983) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.