Sharp subcritical largest-component scale

ID: sharp-subcritical-largest-component-scale

For fixed in , the largest component of a graph has the displayed order with high probability. A dominating Galton-Watson process gives the tail bound by the exponential Markov inequality. For the lower bound, the tree-component expectation in the Erdős-Rényi model diverges at . The disjoint-set covariance factor and the exclusion of overlaps give relative variance tending to zero, so the second moment method supplies a tree component of that order.

New to topics? Read the docs here!