The birth of the giant component

DOI10.1002/RSA.3240040303zbMATH Open0795.05127arXivmath/9310236OpenAlexW2010894431WikidataQ59445805 ScholiaQ59445805MaRDI QIDQ5288006FDOQ5288006

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

Publication date: 22 August 1993

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

Abstract: Limiting distributions are derived for the sparse connected components that are present when a random graph on $n$ vertices has approximately $halfn$ edges. In particular, we show that such a graph consists entirely of trees, unicyclic components, and bicyclic components with probability approaching $sqrt2over3coshsqrt5over18approx0.9325$ as $noinfty$. The limiting probability that it consists of trees, unicyclic components, and at most one other component is approximately 0.9957; the limiting probability that it is planar lies between 0.987 and 0.9998. When a random graph evolves and the number of edges passes $halfn$, its components grow in cyclic complexity according to an interesting Markov process whose asymptotic structure is derived. The probability that there never is more than a single component with more edges than vertices, throughout the evolution, approaches $5pi/18approx0.8727$. A ``uniform model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substantially simpler than the analogous formulas for the classical random graphs of ErdH{o}s and R'enyi. The notions of ``excess and ``deficiency, which are significant characteristics of the generating function as well as of the graphs themselves, lead to a mathematically attractive structural theory for the uniform model. A general approach to the study of stopping configurations makes it possible to sharpen previously obtained estimates in a uniform manner and often to obtain closed forms for the constants of interest. Empirical results are presented to complement the analysis, indicating the typical behavior when $n$ is near 20000.

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

Recommendations

• Birth control for giants
• On a random graph evolving by degrees
• scientific article; zbMATH DE number 1545679
• The Evolution of Random Graphs
• On a random graph with immigrating vertices: Emergence of the giant component

zbMATH Keywords

random graphMarkov processdeficiencygiant componentexcesscyclic complexitygraph evolution

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (only showing first 100 items - show all)

• On the length of a random minimum spanning tree
• Interview with Don Knuth
• Directed cycles and related structures in random graphs. I: Static properties
• Random graphs with forbidden vertex degrees
• On the growth of components with non-fixed excesses
• The size of the giant component in random hypergraphs: a short proof
• The size of the giant joint component in a binomial random double graph
• The maximal length of 2-path in random critical graphs
• Random 2-XORSAT at the Satisfiability Threshold
• Random cubic planar graphs converge to the Brownian sphere
• Analytic description of the phase transition of inhomogeneous multigraphs
• Longest and shortest cycles in random planar graphs
• \(D\cdot E\cdot K=(100)_8\)
• Expected Maximum Block Size in Critical Random Graphs
• The Early Evolution of the Random Graph Process in Planar Graphs and Related Classes
• Kinetic theory and numerical simulations of two-species coagulation
• Parking on Cayley trees and frozen Erdős-Rényi
• Symbolic method and directed graph enumeration
• Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions
• Geometry of the minimal spanning tree of a random 3-regular graph
• Hypergraph matrix models and generating functions
• Parking functions: from combinatorics to probability
• Counting connected graphs with large excess
• Limits of multiplicative inhomogeneous random graphs and Lévy trees: limit theorems
• The critical window in random digraphs
• Concentration of maximum degree in random planar graphs
• The mesoscopic geometry of sparse random maps
• Building a random network with a given expected giant component
• Threshold functions for small subgraphs in simple graphs and multigraphs
• Phase transition in the spanning-hyperforest model on complete hypergraphs
• On the logistic behaviour of the topological ultrametricity of data
• The birth of the strong components
• Speeding up non-Markovian first-passage percolation with a few extra edges
• The Diagonal Poisson Transform and its application to the analysis of a hashing scheme
• Spanning trees in random series-parallel graphs
• Title not available (Why is that?)
• Gracefully degrading consensus and \(k\)-set agreement in directed dynamic networks
• Perturbation theory of a symmetric center within Liénard equations
• Random planar maps and graphs with minimum degree two and three
• On the probability of planarity of a random graph near the critical point
• The pebbling threshold of the square of cliques
• Universality for critical heavy-tailed network models: metric structure of maximal components
• On sorting, heaps, and minimum spanning trees
• Hypercube percolation
• Component structure of the configuration model: barely supercritical case
• Cycles of given lengths in unicyclic components in sparse random graphs
• On the Lambert \(w\) function
• Successive minimum spanning trees
• Critical random graphs and the differential equations technique
• Dynamics of random graphs with bounded degrees
• Heavy-tailed configuration models at criticality
• The number of connected sparsely edged uniform hypergraphs
• The evolution of subcritical Achlioptas processes
• Brownian excursions, critical random graphs and the multiplicative coalescent
• On edge exchangeable random graphs
• Finite size scaling for the core of large random hypergraphs
• Exact enumeration of satisfiable 2-SAT formulae
• Forbidden subgraphs in connected graphs
• 2-Xor revisited: satisfiability and probabilities of functions
• Cluster tails for critical power-law inhomogeneous random graphs
• The random-cluster model on the complete graph
• On the largest component of the random graph at a nearcritical stage
• Tree and forest weights and their application to nonuniform random graphs
• Phase transitions in graphs on orientable surfaces
• Critical behavior in the computational cost of satisfiability testing
• Birth and growth of multicyclic components in random hypergraphs
• The MAX-CUT of sparse random graphs
• Counting strongly-connected, moderately sparse directed graphs
• The critical behavior of random digraphs
• Scaling limit of dynamical percolation on critical Erdős-Rényi random graphs
• A central limit theorem with applications to percolation, epidemics and Boolean models.
• On the \(k\)-orientability of random graphs
• Network evolution and the emergence of structure
• On the phase transition in random simplicial complexes
• Counting connected graphs inside-out
• Two critical periods in the evolution of random planar graphs
• An improved version of cuckoo hashing: average case analysis of construction cost and search operations
• Random 2 XORSAT phase transition
• Critical behavior in inhomogeneous random graphs
• Proof of a series solution for euler's trinomial equation
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• Evolution of the giant component in graphs on orientable surfaces
• Stable graphs: distributions and line-breaking construction
• Phase transition phenomena in random discrete structures
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Cycle structure of percolation on high-dimensional tori
• Title not available (Why is that?)
• A conversation with David J. Aldous
• The phase transition in a random hypergraph
• Expansion of Percolation Critical Points for Hamming Graphs
• The triangle-free process and the Ramsey number \(R(3,k)\)
• The critical random graph, with martingales
• On a random graph evolving by degrees
• Another proof of Wright's inequalities
• Culture and inattentional blindness: a global workspace perspective
• A new approach to the giant component problem
• Perfect hashing
• Edge percolation on a random regular graph of low degree
• Unicyclic components in random graphs
• Cubic graphs and related triangulations on orientable surfaces

This page was built for publication: The birth of the giant component

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5288006)