The birth of the giant component

DOI10.1002/rsa.3240040303zbMath0795.05127arXivmath/9310236WikidataQ59445805 ScholiaQ59445805MaRDI QIDQ5288006

Svante Janson, Tomasz Łuczak, Donald E. Knuth, Boris G. Pittel

Publication date: 22 August 1993

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9310236

zbMATH Keywords

Markov process; random graph; excess; deficiency; giant component; cyclic complexity; graph evolution

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60J99: Markov processes

Related Items

Unnamed Item, Random 2-XORSAT at the Satisfiability Threshold, On the growth of components with non-fixed excesses, Birth and growth of multicyclic components in random hypergraphs, An improved version of cuckoo hashing: average case analysis of construction cost and search operations, Edge percolation on a random regular graph of low degree, The pebbling threshold of the square of cliques, Finite size scaling for the core of large random hypergraphs, On sorting, heaps, and minimum spanning trees, The critical random graph, with martingales, On the \(k\)-orientability of random graphs, On a random graph evolving by degrees, Tree and forest weights and their application to nonuniform random graphs, Phase transition phenomena in random discrete structures, Brownian excursions, critical random graphs and the multiplicative coalescent, The number of connected sparsely edged uniform hypergraphs, Perfect hashing, The phase transition in a random hypergraph, Counting connected graphs inside-out, On the Lambert \(w\) function, On the largest component of the random graph at a nearcritical stage, Directed cycles and related structures in random graphs. I: Static properties, A central limit theorem with applications to percolation, epidemics and Boolean models., Forbidden subgraphs in connected graphs, The random-cluster model on the complete graph, Phase transition in the spanning-hyperforest model on complete hypergraphs, Another proof of Wright's inequalities, D?E?K=(1000)8, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Unnamed Item, The critical behavior of random digraphs, Critical random graphs and the structure of a minimum spanning tree, Random graphs with forbidden vertex degrees, A new approach to the giant component problem

Cites Work

• Wright and Stepanov-Wrigth coefficients
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• On Some Features of the Structure of a Random Graph Near a Critical Point
• Cycles in a random graph near the critical point
• Analytic Inequalities