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.
Articles by others on the same topic
There are currently no matching articles.