×
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 Reviews
Cited in 75 Documents

MSC:

05C80 Random graphs (graph-theoretic aspects)
60J99 Markov processes

Keywords:

giant component; random graph; graph evolution; excess; deficiency; Markov process; cyclic complexity
PDF BibTeX XML Cite
\textit{S. Janson} et al., Random Struct. Algorithms 4, No. 3, 233--358 (1993; Zbl 0795.05127)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

Digital Library of Mathematical Functions:

§16.23(ii) Random Graphs ‣ §16.23 Mathematical Applications ‣ Applications ‣ Chapter 16 Generalized Hypergeometric Functions and Meijer G -Function
§9.13(ii) Generalizations from Integral Representations ‣ §9.13 Generalized Airy Functions ‣ Related Functions ‣ Chapter 9 Airy and Related Functions

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.