The Subcritical Regime
In the random graph \(G(n,p)\), each pair of distinct vertices is joined independently with probability \(p\). We study the sparse choice \(p=c/n\), where \(c\) is fixed as \(n\) grows. When \(0<c<1\), a vertex has approximately \(c\) neighbors on average. Exploring its component therefore resembles a branching process whose mean number of offspring is below one: the exploration tends to die out rather than keep expanding.
Here a component is a maximal connected subgraph, and the component of a vertex \(v\) is denoted \(C(v)\). A statement holds with high probability if its probability tends to \(1\) as \(n\to\infty\). We will establish two conclusions: the expected size of the component of a uniformly chosen vertex tends to \(1/(1-c)\), and the largest component has size at most a constant times \(\log n\) with high probability. The latter is a logarithmic upper bound; this proof does not claim a matching lower bound.
The branching-process model used below is the Galton–Watson process with one initial individual and independent offspring counts having the Poisson distribution with mean \(c\). If \(Z_j\) is the number of individuals in generation \(j\), then \(Z_0=1\) and each individual has a Poisson(\(c\)) number of children. Its total population is \(T=\sum_{j\ge0}Z_j\). Since each individual has expected \(c\) children, conditioning on one generation gives \(\mathbb E Z_j=c^j\).
Expected Component Size
Proof. First, the branching-process total population has expectation $$ \mathbb E T=\sum_{j=0}^{\infty}\mathbb E Z_j=\sum_{j=0}^{\infty}c^j=\frac{1}{1-c}, $$ where the geometric series converges because \(c<1\). We now compare the graph exploration with this process, taking care that convergence of a finite exploration alone does not automatically give convergence of its expectation.
For an upper bound, fix a vertex \(v\). Every vertex in \(C(v)\) is the endpoint of at least one simple path starting at \(v\), with the length-zero path accounting for \(v\) itself. The number of simple paths of length \(k\) starting at \(v\) is at most \((n-1)_k=(n-1)(n-2)\cdots(n-k)\). Each particular path is present with probability \((c/n)^k\). Summing the expected numbers of such paths gives $$ \mathbb E|C(v)|\le 1+\sum_{k=1}^{n-1}(n-1)_k(c/n)^k \le 1+\sum_{k=1}^{n-1}c^k \le \frac{1}{1-c}. $$ The first inequality allows a vertex to be counted more than once, so it is an upper bound. The second uses \((n-1)_k\le n^k\).
For the lower bound, stop the component exploration once it has discovered \(M\) vertices, where \(M\) is any fixed positive integer. For a fixed number of explored vertices, the number of new neighbors of a vertex has a binomial distribution with parameters \(n-O(M)\) and \(c/n\). As \(n\to\infty\), this distribution tends to Poisson(\(c\)); the probability of a collision among the at most \(M\) explored vertices tends to zero. Thus the exploration stopped at \(M\) vertices converges in distribution to the branching process stopped at \(M\) individuals. Since the stopped size is bounded by \(M\), its expectation also converges. In particular, $$ \liminf_{n\to\infty}\mathbb E|C(U_n)|\ge \mathbb E\min(T,M). $$ As \(M\to\infty\), \(\min(T,M)\) increases to \(T\), so its expectations increase to \(\mathbb E T=1/(1-c)\). Combined with the upper bound, this proves the stated limit. \(\square\)
Worked Example: The Mean Total Population at \(c=1/2\)
Take the Poisson branching process with mean offspring \(c=1/2\), the approximation relevant to \(G(n,1/(2n))\). The expected generation sizes are $$ \mathbb E Z_0=1,\qquad \mathbb E Z_1=\frac12,\qquad \mathbb E Z_2=\left(\frac12\right)^2=\frac14,\qquad \mathbb E Z_3=\left(\frac12\right)^3=\frac18. $$ The expected total population is the sum over all generations: $$ \mathbb E T=1+\frac12+\frac14+\frac18+\cdots=\frac{1}{1-1/2}=2. $$ The first four generations contribute \(1+1/2+1/4+1/8=15/8\); the remaining geometric tail is \(1/16+1/32+\cdots=1/8\), giving \(15/8+1/8=2\). This checks the total and illustrates why the limiting expected component size is finite even though the graph has \(n\) vertices.
Why the Largest Component Is at Most Logarithmic
A finite expected component size by itself does not rule out a rare, unusually large component. To bound such events, we use an exponential tail for the branching-process population. The key fact is that a Poisson branching process with mean strictly below one has a finite exponential moment.
Proof. Because the function \(x\mapsto\log x-\lambda(x-1)\) is \(0\) at \(x=1\) and has derivative \(1-\lambda>0\) there, choose \(M>1\) sufficiently close to \(1\) that \(a=\log M-\lambda(M-1)>0\). Choose \(0<\theta\le a\). Let \(T_h\) be the total population through generation \(h\), and set \(F_h=\mathbb E e^{\theta T_h}\). We have \(F_0=e^\theta\le M\). For \(h\ge1\), conditioning on the root's Poisson(\(\lambda\)) number of children gives $$ F_h=e^\theta\exp\!\big(\lambda(F_{h-1}-1)\big). $$ If \(F_{h-1}\le M\), then $$ F_h\le \exp\!\big(\theta+\lambda(M-1)\big)\le \exp(\log M)=M. $$ Induction gives \(F_h\le M\) for all \(h\). Since \(T_h\) increases to \(T\), it follows that \(\mathbb E e^{\theta T}\le M\). On the event \(T\ge k\), \(e^{\theta T}\ge e^{\theta k}\), so $$ \mathbb P(T\ge k)\le e^{-\theta k}\mathbb E e^{\theta T}\le M e^{-\theta k}. $$ This proves the lemma. \(\square\)
To apply this bound to a graph exploration, put \(p=c/n\) and \(q=-\log(1-p)\). A Bernoulli(\(p\)) edge indicator can be coupled below a Poisson(\(q\)) random variable: the indicator that the Poisson variable is positive has probability \(1-e^{-q}=p\), and is at most the Poisson variable. Thus the number of new neighbors discovered while processing a vertex is dominated by a Poisson variable of mean \(nq\). Also \(nq\to c\). Choose a constant \(\lambda\) with \(c<\lambda<1\); for all sufficiently large \(n\), \(nq\le\lambda\). Coupling each exploration step in this way shows that \(|C(v)|\) is dominated by the total population of a Poisson(\(\lambda\)) branching process.
Proof. Use the constants \(M,\theta\) from the lemma for a fixed \(\lambda\) with \(c<\lambda<1\). For all sufficiently large \(n\), the exploration domination and the union bound over the \(n\) possible starting vertices give $$ \mathbb P(L_n\ge k)\le \sum_{v=1}^n\mathbb P(|C(v)|\ge k) \le nM e^{-\theta k}. $$ Choose \(A>1/\theta\) and take \(k=\lceil A\log n\rceil\). Then $$ nM e^{-\theta k}\le M n^{1-\theta A}\longrightarrow 0, $$ because \(1-\theta A<0\). Hence \(L_n=O(\log n)\) with high probability. \(\square\)
Worked Example: Making the Exponential Tail Uniform
Consider \(G(n,1/(2n))\), so \(c=1/2\). Choose \(\lambda=3/4\), which is strictly between \(c\) and \(1\). For \(M=6/5\), $$ \log M-\lambda(M-1)=\log(6/5)-\frac34\cdot\frac15 =\log(6/5)-\frac{3}{20}>0. $$ The inequality follows, for example, from \(\log(1+x)>x/(1+x)\) for \(x>0\), which at \(x=1/5\) gives \(\log(6/5)>1/6>3/20\). Set \(\theta=1/100\), which is less than this positive difference. The lemma therefore gives \(\mathbb P(T\ge k)\le (6/5)e^{-k/100}\) for the dominating branching process.
For \(k=\lceil200\log n\rceil\), the union bound is at most $$ n\cdot\frac65 e^{-k/100} \le \frac65 n e^{-2\log n} =\frac65 n^{-1}, $$ which tends to zero. Thus this choice of constants proves that the largest component is at most \(200\log n\) with probability tending to \(1\), for all sufficiently large \(n\). The constant is deliberately generous; the argument establishes logarithmic order as an upper bound, not a sharp constant.
Worked Example: A Simple-Path Bound in a Finite Graph Model
Take \(G(6,1/12)\), which is \(G(n,c/n)\) with \(n=6\) and \(c=1/2\). Fix vertex \(1\). For each length \(k\), the expected number of simple paths of length \(k\) starting at \(1\) is \((5)_k(1/12)^k\), since there are \((5)_k\) possible vertex sequences and all \(k\) required edges must be present. The values, computed by substituting \(k=1,\ldots,5\), are $$ \frac5{12},\quad \frac{5\cdot4}{12^2}=\frac5{36},\quad \frac{5\cdot4\cdot3}{12^3}=\frac5{144},\quad \frac{5\cdot4\cdot3\cdot2}{12^4}=\frac5{864},\quad \frac{5\cdot4\cdot3\cdot2\cdot1}{12^5}=\frac5{10368}. $$ Every vertex in \(C(1)\) is reached by some simple path from \(1\), so $$ \mathbb E|C(1)|\le 1+\frac5{12}+\frac5{36}+\frac5{144}+\frac5{864}+\frac5{10368} =\frac{16553}{10368}<2. $$ For the arithmetic check, the five fractions have sum \(6185/10368\), so adding \(1=10368/10368\) gives \(16553/10368\). This finite-\(n\) upper bound is consistent with the limiting value \(1/(1-1/2)=2\); it need not equal that limit.
Common Pitfalls and Interpretation
Confusing a mean with a maximum. The limit \(\mathbb E|C(U_n)|\to1/(1-c)\) concerns a uniformly chosen vertex. It does not say that every component has bounded size. The exponential tail and union bound are needed to control all \(n\) possible starting vertices at once.
Using only the branching-process mean for the largest component. Knowing \(\mathbb E T=1/(1-c)\) does not itself give an exponential tail. The exponential-moment argument supplies the stronger estimate that makes the union bound work.
Overstating the conclusion. The proof gives \(L_n=O(\log n)\) with high probability. It does not prove that \(L_n\) is bounded below by a positive constant times \(\log n\). For \(c=0\), every component has size \(1\); the subcritical discussion above assumes \(0<c<1\).
The threshold \(c=1\) is important because the branching-process mean changes from below one to above one there. This tutorial treats only the subcritical side. The results here describe the finite-component regime through the expected size of a typical component and a high-probability upper bound on the largest one.
Check Your Understanding
Use the branching-process comparison and the bounds proved above to answer these questions.
- For \(c=1/3\), what is the limiting expected component size of a uniformly chosen vertex?
- Why does counting simple paths give an upper bound on \(\mathbb E|C(v)|\), rather than an exact count?
- In the exponential-moment proof, where is the assumption \(\lambda<1\) used to choose \(M>1\)?
- Explain why a union bound over starting vertices requires an exponential tail when the target size is proportional to \(\log n\).
- What does the largest-component theorem establish, and what stronger claim does it not establish?