Giant component 2026-10-07
A giant component in a sequence of random graphs on vertices has order proportional to . Its existence can change at a threshold function for a monotone graph property. A giant component need not contain every vertex, and its uniqueness requires proof for the model in question.
Largest component of a graph Created 2026-10-07 Updated 2026-10-14
The largest graph component is one with the most vertices. Ties may be broken arbitrarily; records the order, which is unaffected by the tie. For a sequence of random graphs, the size of its giant component is a central observable.
Fix , , and with . A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most , with high probability. The expected value and variance of the isolated vertex count concentrate it around . A Cayley formula upper bound for connected sets excludes component sizes through a small fixed fraction of ; the empty-graph cut bound excludes the remaining sizes up to . An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is , where . The Markov inequality completes the count of vertices outside the unique large graph component.
Start the Galton-Watson process with one ancestor, , and let every individual independently have a number of offspring distributed as . With independent copies ,
where an empty sum is zero. Extinction is the event that some generation is empty; zero is then absorbing. Write for its probability and for the survival probability.
Set , with . Conditional on the ancestor's number of children, extinction by generation requires independent extinction by generation in every child subtree. Thus
The events increase, so . The probability generating function is continuous on , by domination of by , giving . If is any fixed point, then and monotonicity of inductively gives . Taking limits proves the Galton-Watson extinction fixed point characterization:
In particular it is the smallest nonnegative fixed point wherever the generating series is defined, since it already lies in .
Let , allowing . The probability generating function is increasing and convex, with . If , its tangent inequality gives for , so . If and , there is positive mass at both zero and some integer at least two; strict convexity gives for , again . The exceptional case almost surely has one individual forever, so despite .
If , the left derivative at gives for sufficiently close to . Since , continuity supplies a fixed point below , possibly . Thus survival has positive probability precisely when , apart from deterministic one-child reproduction.
For the random bipartite graph, early exploration of a component alternates between the two vertex classes. Before many vertices are exposed, each discovered vertex has approximately new neighbors in the other class, since tends to that distribution. The two-type mean offspring matrix is
with spectral radius ; equivalently, the mean growth over two generations is . The branching-process comparison therefore predicts a giant component exactly when
For , the local process dies out almost surely, so no linear-sized component is expected; is the critical case, not a positive-survival exception. For , the symmetric survival probability is , where , predicting approximately vertices in the giant. This last passage from local survival to a unique giant is the usual random-graph exploration argument; the branching-process reasoning here supplies the requested threshold explanation rather than a proof of that global theorem.
It suffices to prove the assertion after replacing by : that replacement gives a tighter interval. Thus assume and , and put
At , let count isolated vertices in . The same indicator random variable calculation as for all isolated vertices gives
By the Chebyshev inequality, with high probability. Since eventually, the marked vertices are then not all connected.
At , the logarithmic-regime giant component result applies with and any fixed . Its unique giant component misses vertices. On the event that it misses at most twice that number, exchangeability makes the missed vertex set uniform conditional on its size. A union bound therefore gives
Thus all of is connected at with high probability.
For the uniform random graph process, assign uniform labels to the edges of the complete graph as independent random variables and reveal them in label order. The binomial random graph is the prefix containing the labels at most , where has a binomial distribution with parameters and . Its variance at is , whereas the gap between and the relevant endpoint is . The Chebyshev inequality gives and with high probability, with harmless integer rounding. The monotone graph property that all marked vertices are connected now implies
The marked-set connectivity threshold is lower than the threshold for connecting every vertex, because only about specified vertices need to avoid the small graph components.