Giant component ($|C|=\Theta (n)$)

A giant component in a sequence of random graphs on $n$ vertices has order proportional to $n$. 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.

Suppose $\epsilon =o(1)$ and $\epsilon \ge n^{-1/6}$. The breadth-first exploration of a binomial random graph has deterministic drift $F(t)=\epsilon t-t^2/(2n)+O({\epsilon }^{3}n+\epsilon )$ up to $3\epsilon n$ steps. Its weighted martingale has variance $O(\epsilon n)$. For $h=\sqrt{\epsilon }+(n{\epsilon }^3{)}^{-1/8}$, the Doob L2 maximal inequality makes its maximum smaller than $h{\epsilon }^{2}n/6$ with high probability. Then $A_t>0$ throughout $[h\epsilon n,(2-h)\epsilon n]$, giving a graph component of order $(2-o(1))\epsilon n$.

For the upper expectation bound, let $K=\lceil {\epsilon }^{-3}\rceil$. The dominating binomial branching process has branching survival probability $(2+o(1))\epsilon$ by the binomial branching survival correction. Its branching process conditioned on extinction has mean $1-\epsilon +O({\epsilon }^2+\epsilon /n)$ and total-progeny expected value $O(1/\epsilon )$. Therefore $\mathbb{E}{N}_{\ge K}\le n\rho +O(n/(\epsilon K))$. Since $L_1\le K+N_{\ge K}$ and $K=o(\epsilon n)$, this yields the matching upper bound. Controlling rare large components is necessary to conclude an expected value asymptotic from a typical-size statement.

Fix $k\ge 1$, ${\gamma }_0>1/(k+1)$, and ${\gamma }_0\le \gamma \le 1-\omega (n)/\log n$ with $\omega (n)\to \infty$. A binomial random graph has one giant component of the displayed order and all other graph components are tree components of orders at most $k$, with high probability. The expected value and variance of the isolated vertex count concentrate it around $n^{1-\gamma }\to \infty$. A Cayley formula upper bound for connected sets excludes component sizes $k+1$ through a small fixed fraction of $n$; the empty-graph cut bound excludes the remaining sizes up to $n/2$. An extra-edge count excludes cyclic small graph components. The expected value of the number of vertices in small nonisolated tree components is $O(nd{e}^{-2d})=o(n{e}^{-d})$, where $d=np$. The Markov inequality completes the count of vertices outside the unique large graph component.