40.07.03 · combinatorics / probabilistic-method

The Second-Moment Method and Thresholds for Random Graphs

shipped3 tiersLean: none

Anchor (Master): Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 4, 8, 10 (second moment, Janson, concentration); Erdős-Rényi 1960 *Publ. Math. Inst. Hungar. Acad. Sci.* 5 (the evolution of random graphs, the giant component, connectivity); Bollobás-Thomason 1987 *Combinatorica* 7 (every monotone property has a threshold); Bollobás 1988 *Combinatorica* 8 (chromatic number of $G(n,1/2)$); Glebskii-Kogan-Liogon'kii-Talanov 1969 and Fagin 1976 *J. Symbolic Logic* 41 (the first-order zero-one law)

Intuition Beginner

The first-moment method answers one question: does a thing ever happen? If the average count of some structure is below one, the structure can be missing. But knowing the average is small tells you nothing about whether the structure usually appears, or how reliably. A lottery with an average of one winner per draw might mean exactly one winner every time, or a thousand winners once a century and none in between. The average alone cannot tell these apart.

The second-moment method adds a second number, the spread, and that is enough to settle the matter. If the count has a small average and also a small spread relative to that average, then the count sits tightly near its mean almost every time. So if the mean grows large, the count is large with near-certainty; and a separate use of spread shows that when the mean stays bounded away from zero, the count is rarely zero. Average plus spread pins down behaviour that average alone leaves open.

The payoff is the study of random networks. Build a network by joining each pair of dots with some fixed probability, and watch features switch on as you raise that probability. Below a sharp cutoff a feature is almost surely absent; above it, almost surely present. These cutoffs, called thresholds, are the heartbeat of random-graph theory, and the second moment is the tool that locates them.

Visual Beginner

Picture raising a single dial, the edge probability $p$ , from $0$ up to $1$ , and watching a random network on many dots respond. At first it is a scatter of isolated dots. As the dial turns, small pieces link up; past one mark a single giant clump swallows most dots; past a later mark the last lonely dot finally joins and the whole network becomes one connected piece.

dial position $p$	what the random network looks like
below $1/ n$	tiny scattered pieces, all small
around $1/ n$	a giant clump suddenly forms
below $(ln n) / n$	a few lonely dots remain
above $(ln n) / n$	every dot joined: one connected network

The table reads left to right as a story of sudden change. Each feature does not fade in gradually; it snaps on across a narrow band of the dial. Locating those bands is the whole subject, and the average-plus-spread method is how you find them.

Worked example Beginner

Take a random network on $n = 100$ dots where each of the possible pairs is joined with probability $p$ . We ask: for which $p$ does a triangle (three dots all joined to each other) typically appear?

Step 1. Count the candidate triangles. A triangle is a choice of three dots, and the number of such choices is $(3 100) = 161700$ . Each candidate may or may not have all three of its edges present.

Step 2. Find the chance one fixed candidate is a real triangle. It needs all three of its edges, each present with chance $p$ , so the chance is $p \times p \times p = p^{3}$ .

Step 3. Average the number of triangles. The average count is the number of candidates times the per-candidate chance: $161700 \times p^{3}$ .

Step 4. See where the average crosses one. Set $161700 \times p^{3} = 1$ . Then $p^{3} = 1/161700$ , so $p$ is the cube root of that, about $0.0184$ . Compare this to $1/ n = 1/100 = 0.01$ . The crossing sits a little above $1/ n$ , and indeed the true threshold for triangles is exactly at the scale $p = 1/ n$ .

Step 5. Read off the behaviour. When $p$ is well below $1/100$ , the average triangle count is far below one and triangles are almost surely absent. When $p$ is well above $1/100$ , the average races upward and the spread stays small, so triangles are almost surely present.

What this tells us: the scale $1/ n$ is the tipping point for triangles. Below it, none; above it, many. The average located the scale, and the spread (small here) confirms the count is reliable above the threshold.

Check your understanding Beginner

Formal definition Intermediate+

Fix the Erdős-Rényi random graph $G (n, p)$ : the vertex set is $[n] = {1, \dots, n}$ , and each of the $(2 n)$ potential edges is present independently with probability $p = p (n)$ , absent with probability $1 - p$ . A graph property is a set of graphs closed under isomorphism. We say $G (n, p)$ has a property asymptotically almost surely (a.a.s.) if the probability tends to $1$ as $n \to \infty$ . A property is monotone increasing if adding edges preserves it. The basic probability apparatus — variance, Chebyshev's inequality, indicators — is imported from the probability units $37.0 *$ and applied here, not reproved.

For a random variable $X$ on a probability space, the variance is $Var [X] = E [(X - E [X])^{2}] = E [X^{2}] - E [X]^{2}$ , and the standard deviation is $σ = Var [X]$ .

Chebyshev's inequality. For any $λ > 0$ , $$ \Pr\big(|X - \mathbb{E}[X]| \ge \lambda\big) ;\le; \frac{\mathrm{Var}[X]}{\lambda^2}. $$

The second-moment bound. Let $X \geq 0$ be integer-valued with $E [X] > 0$ . Taking $λ = E [X]$ in Chebyshev's inequality bounds the probability that $X = 0$ : $$ \Pr(X = 0) ;\le; \Pr\big(|X - \mathbb{E}[X]| \ge \mathbb{E}[X]\big) ;\le; \frac{\mathrm{Var}[X]}{\mathbb{E}[X]^2}. $$ Consequently, if a family $X_{n}$ satisfies $Var [X_{n}] = o (E [X_{n}]^{2})$ , then $Pr (X_{n} = 0) \to 0$ — so $X_{n} > 0$ a.a.s. — and moreover $X_{n} \sim E [X_{n}]$ in probability, meaning $X_{n} / E [X_{n}] \to 1$ a.a.s. This is the second-moment method: where the first moment (40.07.01) shows $X = 0$ is possible when $E [X]$ is small, the second moment shows $X = 0$ is improbable when $E [X]$ is large and concentrated.

Threshold function. For a monotone increasing property $P$ , a function $p^{*} (n)$ is a threshold if $G (n, p)$ has $P$ a.a.s. when $p / p^{*} \to \infty$ and lacks $P$ a.a.s. when $p / p^{*} \to 0$ . Thresholds are defined up to constant or slower factors.

For a fixed graph $H$ with $v (H)$ vertices and $e (H)$ edges, the maximum edge density is $$ m(H) ;=; \max_{\substack{H' \subseteq H \ v(H') > 0}} \frac{e(H')}{v(H')}, $$ the maximum taken over all subgraphs $H^{'}$ with at least one vertex. $H$ is balanced if $m (H) = e (H) / v (H)$ (no denser subgraph), and strictly balanced if the maximum is attained only by $H$ itself.

The notation $G (n, p)$ , $E [\cdot]$ , $Var [\cdot]$ , $m (H)$ , $v (H)$ , $e (H)$ , $\sim$ (asymptotic equivalence), and $o (\cdot)$ is registered in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

" $E [X] \to \infty$ already forces $X > 0$ a.a.s." It does not. The count $X$ can have its mass on rare enormous values with $X = 0$ likely: a "clumped" distribution. The variance bound $Var [X] = o (E [X]^{2})$ is precisely what rules this out.
"The threshold for $H$ is $p = n^{- v (H) / e (H)}$ ." That is the first-moment scale only for balanced $H$ . For unbalanced $H$ the densest subgraph appears first, so the true threshold is $p = n^{- 1/ m (H)}$ , governed by $m (H)$ , not the overall ratio $e (H) / v (H)$ .
"Connectivity and the giant component have the same threshold." They differ by a logarithmic factor: the giant component emerges at $p = 1/ n$ , but full connectivity waits until $p = (ln n) / n$ , when the last isolated vertex disappears.
"A small variance means the count is exactly its mean." It means the count is near its mean with high probability. The conclusions are distributional ("a.a.s."), not deterministic.

Key theorem with proof Intermediate+

The signature application is the threshold for the appearance of a fixed subgraph, where the first and second moments together pin down the exact scale ^{[Alon-Spencer Ch. 4]}. We treat the cleanest case, a balanced graph $H$ , where the first moment gives the lower bound (below threshold, $H$ is absent) and the second moment gives the upper bound (above threshold, $H$ appears).

Theorem (subgraph appearance threshold; Erdős-Rényi 1960, Bollobás). Let $H$ be a balanced graph with $v = v (H)$ vertices and $e = e (H) \geq 1$ edges, so $m (H) = e / v$ . Then $p^(n) = n^{-1/m(H)} = n^{-v/e} $i s a t h r es h o l df or t h e p r o p er t y "$ G(n,p) $co n t ain s a co p y o f$ H $" : i f$ p = o(n^{-v/e}) $t h e na . a . s .$ G(n,p) $ha s n oco p y o f$ H $, an d i f$ n^{-v/e} = o(p) $t h e na . a . s .$ G(n,p) $ha s a co p y o f$ H$.*

Proof. Let $X$ count copies of $H$ in $G (n, p)$ . Index potential copies by injections of $V (H)$ into $[n]$ up to the automorphisms of $H$ ; the number of potential copies is $Θ (n^{v})$ , since it is $n^{v} / a$ with $a = ∣ Aut (H) ∣ \cdot (overcount)$ a constant. Each fixed copy is present when its $e$ edges are all present, probability $p^{e}$ . By linearity of expectation, $$ \mathbb{E}[X] = \Theta(n^v) \cdot p^e = \Theta\big(n^v p^e\big). $$

Lower (first moment). If $p = o (n^{- v / e})$ then $n^{v} p^{e} = o (1)$ , so $E [X] \to 0$ . Since $X$ is a non-negative integer, $Pr (X \geq 1) \leq E [X] \to 0$ , so a.a.s. $X = 0$ .

Upper (second moment). Suppose $n^{- v / e} = o (p)$ , so $E [X] = Θ (n^{v} p^{e}) \to \infty$ . We show $Var [X] = o (E [X]^{2})$ . Write $X = \sum_{α} 1_{α}$ over potential copies $α$ . Then $$ \mathrm{Var}[X] = \sum_{\alpha, \beta} \big(\Pr(\alpha \wedge \beta) - \Pr(\alpha)\Pr(\beta)\big). $$ Pairs $(α, β)$ sharing no edge contribute $0$ (independence). Group the rest by the subgraph $J = H_{α} \cap H_{β}$ on the shared vertices, which has some $j$ vertices and $f \geq 1$ edges. The number of such pairs is $Θ (n^{2 v - j})$ , and the joint probability is $p^{2 e - f}$ (the $2 e - f$ distinct edges). So $$ \mathrm{Var}[X] \le \sum_{J} \Theta\big(n^{2v - j} p^{2e - f}\big) = \mathbb{E}[X]^2 \sum_J \Theta\big(n^{-j} p^{-f}\big), $$ using $E [X]^{2} = Θ (n^{2 v} p^{2 e})$ . For each shared piece $J \subseteq H$ with $j$ vertices and $f$ edges, balancedness gives $f / j \leq e / v$ , i.e. $n^{- j} p^{- f} \leq n^{- j} (n^{- v / e})^{- f} (p / n^{- v / e})^{- f} = n^{f v / e - j} ω^{- f}$ where $ω = p / n^{- v / e} \to \infty$ . Since $f \leq j e / v$ gives $f v / e - j \leq 0$ , each term is $O (ω^{- f}) = o (1)$ . The number of shapes $J$ is bounded by a constant. Hence $Var [X] = o (E [X]^{2})$ , and the second-moment bound gives $Pr (X = 0) \to 0$ : a.a.s. a copy of $H$ exists. $□$

Bridge. This proof builds toward the whole theory of random-graph evolution: the same two-sided template — first moment kills the count below threshold, second moment forces concentration above it — appears again in the connectivity and clique-number arguments below, and the foundational reason it works is that variance decomposes over pairs of copies, with only edge-sharing pairs contributing covariance. The role of $m (H)$ is exactly this: balancedness is the condition $f / j \leq e / v$ that makes every shared-piece term vanish, so $m (H)$ is the densest sub-piece that could appear first, which is why the threshold is $n^{- 1/ m (H)}$ rather than the naive $n^{- v / e}$ — for unbalanced $H$ these differ, and the bridge is that the densest subgraph dictates the timing. This is dual to the first-moment picture of 40.07.01: there a small mean permits absence, here a large concentrated mean forces presence, and putting these together gives a sharp threshold where the two verdicts meet. The central insight is that the second moment converts the first moment's "possible" into "typical", and the appearance threshold for subgraphs generalises to thresholds for every monotone property by Bollobás-Thomason.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that $p = 1/ n$ is the threshold scale at which the expected number of triangles in $G (n, p)$ passes from $o (1)$ to $\to \infty$ , by computing $E [# triangles]$ and analysing $p = c / n$ for constant $c$ .

Hint

There are $(3 n)$ candidate triangles, each present with probability $p^{3}$ . Substitute $p = c / n$ and simplify the leading term.

Answer

The number of candidate triangles is $(3 n) = \frac{n ( n - 1 ) ( n - 2 )}{6} \sim n^{3} /6$ , each present with probability $p^{3}$ . By linearity, $E [X] = (3 n) p^{3} \sim n^{3} p^{3} /6$ . With $p = c / n$ this is $\sim (c n / n)^{3} \cdot n^{3} / (6)$ ; more carefully $n^{3} (c / n)^{3} /6 = c^{3} /6$ , a constant. So at the exact scale $p = c / n$ the expected number of triangles tends to the constant $c^{3} /6$ — the threshold window. For $p = ω (1/ n)$ , $E [X] = Θ (n^{3} p^{3}) \to \infty$ ; for $p = o (1/ n)$ , $E [X] \to 0$ . So $1/ n$ is the threshold, and within the window the triangle count converges to a Poisson law with mean $c^{3} /6$ . Rubric: full credit for $E [X] \sim n^{3} p^{3} /6$ , the constant limit $c^{3} /6$ at $p = c / n$ , and the two-sided behaviour off the window.

Exercise 4 (medium, symbolic).

Let $H$ be the "kite": a triangle $K_{3}$ with one extra pendant edge attached to a vertex ( $v = 4$ , $e = 4$ ). Compute $m (H)$ and the appearance threshold, and verify $H$ is unbalanced.

Hint

Compare $e (H) / v (H) = 4/4 = 1$ against the density of the triangle subgraph $K_{3}$ inside it, $3/3 = 1$ . Then check whether the maximum is attained at $H$ or at a proper subgraph.

Answer

The whole kite has $e / v = 4/4 = 1$ . Its triangle subgraph $K_{3}$ has $f / j = 3/3 = 1$ as well, so $m (H) = max (1, 1, \dots) = 1$ , but the maximum is attained both by $H$ and by the proper subgraph $K_{3}$ , so $H$ is not strictly balanced — it is balanced but not strictly (the densest density is shared). The threshold is $p^{*} = n^{- 1/ m (H)} = n^{- 1} = 1/ n$ , the same scale as the triangle, because the triangle is the densest piece and must appear first; the pendant edge then attaches with probability bounded away from zero once a triangle exists at $p ≫ 1/ n$ . Rubric: full credit for $m (H) = 1$ , the threshold $1/ n$ , and the observation that the triangle subgraph ties the overall density (balanced but not strictly balanced), so the densest subgraph governs timing.

Exercise 7 (hard, symbolic).

Prove that $p = (ln n) / n$ is a threshold for the disappearance of isolated vertices: if $p = (ln n + c_{n}) / n$ with $c_{n} \to - \infty$ then a.a.s. an isolated vertex exists, and if $c_{n} \to + \infty$ then a.a.s. none does. Use the first moment for one direction and the second moment for the other.

Hint

Let $X$ count isolated vertices; $E [X] = n (1 - p)^{n - 1} \approx e^{- c_{n}}$ . For $c_{n} \to + \infty$ use $E [X] \to 0$ (first moment). For $c_{n} \to - \infty$ use $E [X] \to \infty$ plus a variance bound: two distinct vertices are both isolated with probability $(1 - p)^{2 n - 3}$ .

Answer

Let $X = \sum_{v} 1 [v isolated]$ . Then $E [X] = n (1 - p)^{n - 1}$ , and with $p = (ln n + c_{n}) / n$ , $E [X] \sim n e^{- p n} = n e^{- (l n n + c_{n})} = e^{- c_{n}}$ . Case $c_{n} \to + \infty$ : $E [X] \sim e^{- c_{n}} \to 0$ , so $Pr (X \geq 1) \leq E [X] \to 0$ — no isolated vertex a.a.s. Case $c_{n} \to - \infty$ : $E [X] \sim e^{- c_{n}} \to \infty$ . For the second moment, $E [X^{2}] = E [X] + n (n - 1) (1 - p)^{2 (n - 2) + 1}$ , since two fixed vertices $u, v$ are both isolated iff all $2 n - 3$ edges at $u$ or $v$ are absent (the edge $uv$ counted once). Thus $E [X^{2}] = E [X] + n (n - 1) (1 - p)^{2 n - 3}$ . Now $n (n - 1) (1 - p)^{2 n - 3} = (1 + o (1)) [n (1 - p)^{n - 1}]^{2} (1 - p)^{- 1} = (1 + o (1)) E [X]^{2}$ , since $(1 - p)^{- 1} \to 1$ . So $E [X^{2}] = (1 + o (1)) E [X]^{2} + E [X]$ , giving $Var [X] = o (E [X]^{2}) + E [X] = o (E [X]^{2})$ as $E [X] \to \infty$ . By the second-moment bound $Pr (X = 0) \to 0$ : an isolated vertex exists a.a.s. Rubric: full credit for $E [X] \sim e^{- c_{n}}$ , the first-moment direction, the joint-isolation probability $(1 - p)^{2 n - 3}$ , and the variance estimate forcing $Var = o (E [X]^{2})$ .

Exercise 8 (hard, short-answer).

Explain in one paragraph why the first-moment method alone can prove a property is absent below threshold but cannot prove it present above threshold, and exactly what the second moment supplies to close that gap.

Hint

Below threshold, $E [X] \to 0$ and Markov gives $Pr (X \geq 1) \to 0$ . Above threshold $E [X] \to \infty$ , but a large mean is compatible with $Pr (X = 0)$ bounded away from zero unless variance is controlled.

Answer

Below the threshold the expected count tends to zero, and Markov's inequality $Pr (X \geq 1) \leq E [X]$ immediately forces the count to be zero a.a.s. — the first moment alone proves absence. Above the threshold the expected count tends to infinity, but a large mean does not by itself prevent $X = 0$ : the mass of $X$ could concentrate on rare, very large values while $X = 0$ remains likely (a "clumped" distribution), so Markov in the other direction gives nothing. The second moment supplies the missing control. Chebyshev's inequality bounds $Pr (X = 0) \leq Var [X] / E [X]^{2}$ , so once one shows the variance is $o (E [X]^{2})$ — typically by checking that pairs of copies of $H$ rarely share edges, so covariances are small — the count cannot vanish and in fact concentrates on its mean. The asymmetry is structural: proving "never happens" needs only an upper bound on a non-negative mean, while proving "always happens" needs a lower bound on the bulk of the distribution, which is a second-moment (spread) statement, not a first-moment (mean) one. Rubric: full credit for the Markov absence argument, the clumping obstruction to presence, and the role of Chebyshev/variance in forcing concentration.

Advanced results Master

The second moment locates individual thresholds; assembling them produces the Erdős-Rényi picture of a random graph evolving as $p$ increases, together with the structural theorems that organise it.

Theorem 1 (existence of thresholds; Bollobás-Thomason 1987). Every nontrivial monotone increasing graph property $P$ has a threshold function $p^{*} (n)$ : $G (n, p)$ has $P$ a.a.s. when $p / p^{*} \to \infty$ and lacks it a.a.s. when $p / p^{*} \to 0$ ^{[Bollobás-Thomason 1987]}. The proof needs no second-moment computation — it is a soft monotonicity-and-coupling argument: the probability $f (p) = Pr (G (n, p) \in P)$ is non-decreasing in $p$ , and a union of $k$ independent copies of $G (n, p)$ stochastically dominates $G (n, 1 - (1 - p)^{k}) \leq G (n, k p)$ , so the band where $f$ rises from $ε$ to $1 - ε$ has width bounded by a constant factor. Thresholds always exist; the work is computing where they sit, and the second moment is the standard instrument for that.

Theorem 2 (subgraph threshold, general $H$ ). For an arbitrary fixed graph $H$ with at least one edge, $p^{*} = n^{- 1/ m (H)}$ with $m (H) = max_{H^{'} \subseteq H} e (H^{'}) / v (H^{'})$ is the threshold for containing $H$ ^{[Alon-Spencer Ch. 4]}. The first moment for the densest subgraph $H_{0}$ achieving $m (H)$ gives the lower bound (if $p ≪ n^{- 1/ m (H)}$ then even $H_{0}$ is absent, so $H$ is); the second moment applied to $H_{0}$ gives its appearance, after which sparser attachments follow. For unbalanced $H$ , the overall ratio $e (H) / v (H) < m (H)$ would predict a later threshold, but the dense core $H_{0}$ appears first and dictates the timing — the reason the threshold is governed by $m (H)$ , not $e (H) / v (H)$ .

Theorem 3 (connectivity and isolated vertices; Erdős-Rényi 1960). At $p = (ln n + c) / n$ , the number of isolated vertices converges in distribution to Poisson with mean $λ = e^{- c}$ , and $G (n, p)$ is connected if and only if it has no isolated vertices a.a.s.; hence $Pr (G (n, p) connected) \to e^{- e^{- c}}$ ^{[Erdős-Rényi 1960]}. The coupon-collector heuristic explains the $(ln n) / n$ scale: each vertex needs at least one of its $n - 1$ potential edges, an event of probability $\approx 1 - e^{- p n}$ , and demanding all $n$ vertices succeed is a coupon-collector problem whose threshold sits at $p n = ln n$ . Connectivity is thus the disappearance of the last isolated vertex, the dominant obstruction once the giant component has formed.

Theorem 4 (the giant component; Erdős-Rényi 1960). Write $p = c / n$ . For $c < 1$ all components of $G (n, p)$ have size $O (lo g n)$ a.a.s.; at $c = 1$ the largest component has size $Θ (n^{2/3})$ ; for $c > 1$ there is a unique giant component of size $(β + o (1)) n$ where $β = β (c) > 0$ is the survival probability of a Poisson $(c)$ branching process (the least root of $1 - β = e^{- c β}$ ), all other components being $O (lo g n)$ ^{[Erdős-Rényi 1960]}. The critical window is $p = 1/ n + λ n^{- 4/3}$ : inside it the largest components have size $Θ (n^{2/3})$ and a rich limiting structure (Aldous 1997). This phase transition — the "double jump" — is the most studied feature of the model and the prototype for percolation transitions.

Theorem 5 (clique and chromatic number of $G (n, 1/2)$ ; Bollobás 1988). The clique number $ω (G (n, 1/2))$ is concentrated on two consecutive values around $2 lo g_{2} n$ : there is an integer $k_{0} = k_{0} (n) \approx 2 lo g_{2} n$ with $ω \in {k_{0}, k_{0} + 1}$ a.a.s. ^{[Bollobás 1988]}. The second moment proves $ω \geq k_{0}$ (the expected number of $k_{0}$ -cliques tends to infinity with small variance), and the first moment proves $ω \leq k_{0} + 1$ . The chromatic number satisfies $χ (G (n, 1/2)) = (1 + o (1)) n / (2 lo g_{2} n)$ a.a.s., proved by an Azuma martingale concentration on the chromatic number together with the clique/independence bound — a result detailed in the co-produced concentration unit 40.07.05.

Theorem 6 (zero-one law; Glebskii et al. 1969, Fagin 1976). For every property $P$ expressible in the first-order language of graphs (quantifiers over vertices, the adjacency relation, equality), $Pr (G (n, 1/2) ⊨ P) \to 0$ or $\to 1$ as $n \to \infty$ ^{[Fagin 1976]}. The mechanism is the extension axioms $A_{r, s}$ : "for every $r$ vertices and $s$ vertices there is a further vertex adjacent to the first $r$ and not the last $s$ ", each of which holds a.a.s. in $G (n, 1/2)$ by a second-moment / direct calculation. Any first-order sentence is decided by finitely many extension axioms via an Ehrenfeucht-Fraïssé back-and-forth, so its limiting probability is $0$ or $1$ . The law fails for $p = p (n)$ at threshold scales (where subgraph-appearance sentences have intermediate limiting probability) and for monadic second-order logic.

Synthesis. Putting these together, the second-moment method is the foundational reason the random graph has a sharp evolutionary picture rather than a blurry one: the first moment of 40.07.01 marks where each feature could appear, and the variance bound $Var [X] = o (E [X]^{2})$ converts that into the statement that it does appear, abruptly, at a threshold. This is exactly the duality that organises the chapter — first moment forbids below, second moment compels above, and the two verdicts meet at $p^{*}$ — and it generalises from one feature to all of them: subgraph appearance at $n^{- 1/ m (H)}$ , connectivity at $(ln n) / n$ , the giant component at $1/ n$ , the clique number at $2 lo g_{2} n$ , each a threshold located by the same mean-and-variance pincer. Bollobás-Thomason shows the existence of thresholds is automatic for monotone properties, so the real content is always the location, and the central insight is that location is a second-moment computation. The zero-one law is the logical shadow of this: at $p = 1/2$ every first-order feature has limiting probability $0$ or $1$ , the extension axioms holding a.a.s. by the same variance control. The bridge onward is that when copies of $H$ share many edges the plain second moment is too weak and one needs Janson's inequality (the co-produced 40.07.07) for sharp upper tail bounds, and when one wants concentration of a Lipschitz graph parameter rather than a count one needs the martingale machinery of the co-produced 40.07.05 — both are the next refinements of the variance idea introduced here.

Full proof set Master

Proposition 1 (second-moment bound from Chebyshev). Let $X \geq 0$ be integer-valued with $E [X] > 0$ . Then $Pr (X = 0) \leq Var [X] / E [X]^{2}$ . Consequently if a sequence $X_{n}$ has $Var [X_{n}] = o (E [X_{n}]^{2})$ then $X_{n} > 0$ a.a.s. and $X_{n} / E [X_{n}] \to 1$ in probability.

Proof. The event ${X = 0}$ implies $∣ X - E [X] ∣ = E [X]$ , hence ${X = 0} \subseteq {∣ X - E [X] ∣ \geq E [X]}$ . Chebyshev's inequality with $λ = E [X]$ gives $Pr (X = 0) \leq Pr (∣ X - E [X] ∣ \geq E [X]) \leq Var [X] / E [X]^{2}$ . If $Var [X_{n}] = o (E [X_{n}]^{2})$ this tends to $0$ , so $X_{n} > 0$ a.a.s. For the second clause, fix $ε > 0$ and apply Chebyshev with $λ = ε E [X_{n}]$ : $Pr (∣ X_{n} - E [X_{n}] ∣ \geq ε E [X_{n}]) \leq Var [X_{n}] / (ε^{2} E [X_{n}]^{2}) \to 0$ , so $X_{n} / E [X_{n}] \to 1$ in probability. $□$

Proposition 2 (subgraph threshold, balanced case). Let $H$ be balanced with $v$ vertices, $e \geq 1$ edges. Then $X = # {copies of H in G (n, p)}$ has $E [X] = Θ (n^{v} p^{e})$ , and if $p n^{v / e} \to \infty$ then $Var [X] = o (E [X]^{2})$ , so $X > 0$ a.a.s.

Proof. The number of potential copies is $c_{H} n^{v} (1 + o (1))$ with $c_{H} = 1/∣ Aut (H) ∣$ times the labelling constant, each present with probability $p^{e}$ , so $E [X] = Θ (n^{v} p^{e})$ by linearity. Writing $X = \sum_{α} 1_{α}$ , the covariance of two copies $α, β$ vanishes unless they share at least one edge. Group sharing pairs by the isomorphism type of the overlap $J = α \cap β$ (a subgraph of $H$ ) with $j = v (J) \geq 1$ vertices and $f = e (J) \geq 1$ edges. The number of such ordered pairs is $Θ (n^{2 v - j})$ and $Pr (α \land β) = p^{2 e - f}$ , so their contribution to $Var [X]$ is $Θ (n^{2 v - j} p^{2 e - f})$ . Dividing by $E [X]^{2} = Θ (n^{2 v} p^{2 e})$ gives $Θ (n^{- j} p^{- f})$ . Balancedness means $f / j \leq e / v$ for every subgraph $J$ , i.e. $f \leq j e / v$ ; with $ω := p n^{v / e} \to \infty$ one has $n^{- j} p^{- f} = n^{- j} (ω n^{- v / e})^{- f} = ω^{- f} n^{f v / e - j} \leq ω^{- f} \to 0$ , since $f v / e - j \leq 0$ . Summing over the constant number of overlap types, $Var [X] / E [X]^{2} \to 0$ , and Proposition 1 yields $X > 0$ a.a.s. $□$

Proposition 3 (first-moment lower bound for subgraphs). If $p = o (n^{- v / e})$ for the densest subgraph ratio, then a.a.s. $G (n, p)$ contains no copy of $H$ .

Proof. Let $H_{0} \subseteq H$ attain $m (H) = e (H_{0}) / v (H_{0})$ , with $v_{0}$ vertices and $e_{0}$ edges. Any copy of $H$ contains a copy of $H_{0}$ , so it suffices that $G (n, p)$ has no copy of $H_{0}$ a.a.s. Let $Y$ count copies of $H_{0}$ ; $E [Y] = Θ (n^{v_{0}} p^{e_{0}})$ . If $p = o (n^{- 1/ m (H)}) = o (n^{- v_{0} / e_{0}})$ then $n^{v_{0}} p^{e_{0}} = (n^{v_{0} / e_{0}} p)^{e_{0}} = o (1)$ , so $E [Y] \to 0$ and $Pr (Y \geq 1) \leq E [Y] \to 0$ . Hence a.a.s. no copy of $H_{0}$ , so a.a.s. no copy of $H$ . $□$

Proposition 4 (Poisson limit for isolated vertices). At $p = (ln n + c) / n$ , the number $X$ of isolated vertices in $G (n, p)$ converges in distribution to Poisson $(e^{- c})$ .

Proof. The factorial moments converge to those of Poisson $(λ)$ with $λ = e^{- c}$ . The $r$ -th factorial moment is $E [(X)_{r}] = (n)_{r} Pr (r fixed vertices all isolated)$ . For $r$ fixed vertices to be isolated, all edges incident to them — there are $r (n - 1) - (2 r)$ of them — must be absent, probability $(1 - p)^{r (n - 1) - (2 r)}$ . Thus $E [(X)_{r}] = (n)_{r} (1 - p)^{r (n - 1) - (2 r)} = (1 + o (1)) n^{r} (1 - p)^{r (n - 1)} = (1 + o (1)) (n (1 - p)^{n - 1})^{r}$ , since the correction $(1 - p)^{- (2 r)} \to 1$ for fixed $r$ . As $n (1 - p)^{n - 1} \to e^{- c} = λ$ , $E [(X)_{r}] \to λ^{r}$ , the $r$ -th factorial moment of Poisson $(λ)$ . By the method of moments (factorial moments determine the Poisson limit), $X d Poisson (λ)$ . $□$

Proposition 5 (clique number lower bound for $G (n, 1/2)$ ). Let $k = k (n)$ satisfy $E [X_{k}] \to \infty$ where $X_{k}$ counts $k$ -cliques in $G (n, 1/2)$ , $E [X_{k}] = (k n) 2^{- (2 k)}$ . If additionally $Var [X_{k}] = o (E [X_{k}]^{2})$ , then $ω (G (n, 1/2)) \geq k$ a.a.s.

Proof. By the second-moment bound (Proposition 1), $Var [X_{k}] = o (E [X_{k}]^{2})$ gives $Pr (X_{k} = 0) \to 0$ , so a $k$ -clique exists a.a.s., i.e. $ω \geq k$ . The variance hypothesis holds for $k = (2 - ε) lo g_{2} n$ : two $k$ -sets sharing $i$ vertices have joint-clique probability $2^{- 2 (2 k) + (2 i)}$ , and the sum $\sum_{i} (i k) (k - i n - k) 2^{(2 i)} / (k n)$ over $i \geq 2$ is $o (1)$ relative to $E [X_{k}]^{2}$ when $k \leq (2 - ε) lo g_{2} n$ , because the dominant overlap $i = 0, 1$ contributes $(1 + o (1)) E [X_{k}]^{2}$ . Hence $ω \geq (2 - ε) lo g_{2} n$ a.a.s.; combined with the first-moment upper bound $E [X_{k^{'}}] \to 0$ at $k^{'} = (2 + ε) lo g_{2} n$ , the clique number concentrates at $2 lo g_{2} n$ . $□$

Connections Master

The first-moment method of 40.07.01 supplies the lower half of every threshold proved here: below threshold a count with mean tending to zero is absent a.a.s. by Markov, exactly the half that the second moment cannot give. This unit is the dual completion — the second moment compels presence above threshold where the first moment only permits absence below it — so the two methods together pin each random-graph feature to a sharp $p^{*}$ , and the appearance-of- $H$ argument runs the first moment on the densest subgraph and the second moment on the whole.
The Borel-Cantelli lemmas and Kolmogorov zero-one law of 37.02.01 are the infinitary analogue of the finite zero-one law stated here: Borel-Cantelli converts summability of probabilities into almost-sure absence (a first-moment statement along a sequence), and the second-moment / second Borel-Cantelli direction gives almost-sure recurrence, the same mean-and-variance pincer transposed from "a.a.s. as $n \to \infty$ " to "almost surely along an infinite sequence of trials". The extension-axiom mechanism behind Fagin's law is the combinatorial counterpart of Kolmogorov's tail triviality.
The concentration of the chromatic number and the two-point concentration of the clique number, sketched in Theorem 5, are carried out in full in the co-produced 40.07.05 via Azuma-Hoeffding martingale inequalities: the second moment here proves the clique number is at least $2 lo g_{2} n$ , while the martingale method proves the chromatic number is concentrated in an interval of width $o (n / lo g n)$ — the variance idea pushed from counts to Lipschitz graph functionals. The sharp upper-tail bound that the plain second moment misses, when copies of $H$ share many edges, is supplied by Janson's inequality in the co-produced 40.07.07, the natural successor to this unit for fine threshold and large-deviation questions.

Historical & philosophical context Master

The systematic theory of random graphs is the creation of Paul Erdős and Alfréd Rényi, whose 1960 memoir On the evolution of random graphs ^{[Erdős-Rényi 1960]} introduced the model $G (n, M)$ (and the closely related $G (n, p)$ ), proved the threshold for the appearance of each fixed subgraph, identified the connectivity threshold $(ln n) / n$ through the disappearance of isolated vertices with its Poisson limit, and discovered the abrupt birth of a giant component at $M = n /2$ — the "double jump" from logarithmic to $n^{2/3}$ to linear largest-component size. The second-moment method as the standard instrument for the upper half of a threshold was already implicit in their estimates and was codified, with Chebyshev's inequality at its core, in the subsequent literature; Erdős had used the first moment in his 1947 Ramsey note, and the second moment is its natural completion.

The structural theorems came later. Béla Bollobás and Andrew Thomason proved in 1987 that every monotone property has a threshold ^{[Bollobás-Thomason 1987]}, detaching the existence of thresholds from their computation. Bollobás determined the asymptotic chromatic number of $G (n, 1/2)$ in 1988 ^{[Bollobás 1988]} using martingale concentration, and the two-point concentration of the clique number was established by Bollobás and Erdős and by Matula in the 1970s. The first-order zero-one law was proved independently by Glebskii, Kogan, Liogon'kii, and Talanov in 1969 and by Ronald Fagin in 1976 ^{[Fagin 1976]}, via the extension axioms and a back-and-forth argument; it is a foundational result in finite model theory, linking logic, probability, and combinatorics.

Bibliography Master

@article{erdosrenyi1960,
  author  = {Erd{\H{o}}s, Paul and R{\'e}nyi, Alfr{\'e}d},
  title   = {On the evolution of random graphs},
  journal = {Publications of the Mathematical Institute of the Hungarian Academy of Sciences},
  volume  = {5},
  pages   = {17--61},
  year    = {1960}
}

@article{bollobasthomason1987,
  author  = {Bollob{\'a}s, B{\'e}la and Thomason, Andrew},
  title   = {Threshold functions},
  journal = {Combinatorica},
  volume  = {7},
  number  = {1},
  pages   = {35--38},
  year    = {1987}
}

@article{bollobas1988chromatic,
  author  = {Bollob{\'a}s, B{\'e}la},
  title   = {The chromatic number of random graphs},
  journal = {Combinatorica},
  volume  = {8},
  number  = {1},
  pages   = {49--55},
  year    = {1988}
}

@article{fagin1976,
  author  = {Fagin, Ronald},
  title   = {Probabilities on finite models},
  journal = {Journal of Symbolic Logic},
  volume  = {41},
  number  = {1},
  pages   = {50--58},
  year    = {1976}
}

@article{glebskii1969,
  author  = {Glebskii, Y. V. and Kogan, D. I. and Liogon'kii, M. I. and Talanov, V. A.},
  title   = {Range and degree of realizability of formulas in the restricted predicate calculus},
  journal = {Cybernetics},
  volume  = {5},
  pages   = {142--154},
  year    = {1969}
}

@article{aldous1997critical,
  author  = {Aldous, David},
  title   = {Brownian excursions, critical random graphs and the multiplicative coalescent},
  journal = {Annals of Probability},
  volume  = {25},
  number  = {2},
  pages   = {812--854},
  year    = {1997}
}

@book{bollobas2001random,
  author    = {Bollob{\'a}s, B{\'e}la},
  title     = {Random Graphs},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@book{friezekaronski2016,
  author    = {Frieze, Alan and Karo{\'n}ski, Micha{\l}},
  title     = {Introduction to Random Graphs},
  publisher = {Cambridge University Press},
  year      = {2016}
}

@book{alonspencer2016,
  author    = {Alon, Noga and Spencer, Joel H.},
  title     = {The Probabilistic Method},
  edition   = {4},
  publisher = {Wiley},
  year      = {2016}
}

Prerequisites

40.07.01

Tier anchors

beginner: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 4 (the second moment, the random graph $G(n,p)$, threshold functions, the appearance of small subgraphs); a 'spread-out versus clumped' analogy for why a small average can still mean zero (first moment) or many (second moment)
intermediate: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 4 §4.1-4.5 (Chebyshev and the second-moment bound, $G(n,p)$, threshold for containing a fixed subgraph $p = n^{-1/m(H)}$, threshold for isolated vertices and connectivity $p = \ln n / n$); Bollobás 2001 *Random Graphs* 2e (Cambridge) Ch. 3-4; Frieze-Karoński 2016 *Introduction to Random Graphs* (Cambridge) Ch. 1-5
master: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 4, 8, 10 (second moment, Janson, concentration); Erdős-Rényi 1960 *Publ. Math. Inst. Hungar. Acad. Sci.* 5 (the evolution of random graphs, the giant component, connectivity); Bollobás-Thomason 1987 *Combinatorica* 7 (every monotone property has a threshold); Bollobás 1988 *Combinatorica* 8 (chromatic number of $G(n,1/2)$); Glebskii-Kogan-Liogon'kii-Talanov 1969 and Fagin 1976 *J. Symbolic Logic* 41 (the first-order zero-one law)

References

Alon, N. & Spencer, J. H. — The Probabilistic Method · Wiley, 4th edition (2016). Chapter 4 develops the second-moment method: Chebyshev's inequality $\Pr(|X - \mu| \ge \lambda) \le \sigma^2/\lambda^2$, the second-moment existence/concentration bound (if $\mathrm{Var}[X] = o(\mathbb{E}[X]^2)$ then $X > 0$ and $X \sim \mathbb{E}[X]$ a.a.s.), the Erdős-Rényi random graph $G(n,p)$, threshold functions for monotone properties, the threshold $p = n^{-1/m(H)}$ for the appearance of a fixed subgraph $H$ (balanced versus unbalanced, $m(H) = \max_{H' \subseteq H} e(H')/v(H')$), the threshold $p = \ln n / n$ for the disappearance of isolated vertices and for connectivity with the Poisson limit, and a statement of the giant-component phase transition at $p = 1/n$.
Erdős, P. & Rényi, A. — On the evolution of random graphs · *Publications of the Mathematical Institute of the Hungarian Academy of Sciences* 5 (1960), 17-61. The founding study of $G(n, M)$ and $G(n,p)$: the threshold for the appearance of each fixed subgraph, the double-jump phase transition of the largest component at $M = n/2$ (i.e. $p = 1/n$) from $O(\log n)$ to $\Theta(n^{2/3})$ to a unique giant of size $\Theta(n)$, the connectivity threshold $p = \ln n / n$ via isolated vertices, and the Poisson limit law for the number of isolated vertices.
Bollobás, B. & Thomason, A. — Threshold functions · *Combinatorica* 7 (1987), 35-38. Every nontrivial monotone increasing graph property has a threshold function $p^*(n)$: there is a function $p^*$ such that $G(n,p)$ has the property a.a.s. when $p / p^* \to \infty$ and lacks it a.a.s. when $p / p^* \to 0$. The proof uses a coupling/subadditivity argument on the probability as a monotone function of $p$.
Bollobás, B. — The chromatic number of random graphs · *Combinatorica* 8 (1988), 49-55. The chromatic number of $G(n,1/2)$ is asymptotically $n / (2\log_2 n)$, with the clique number $\omega(G(n,1/2))$ concentrated on two values around $2\log_2 n$, proved by a second-moment estimate on the number of $k$-cliques together with a martingale concentration (Azuma) argument.
Fagin, R. — Probabilities on finite models · *Journal of Symbolic Logic* 41 (1976), 50-58. The first-order zero-one law: for every property $P$ expressible in the first-order language of graphs, the probability that $G(n, 1/2)$ satisfies $P$ tends to $0$ or to $1$ as $n \to \infty$. Independently proved by Glebskii, Kogan, Liogon'kii, and Talanov (1969). The proof uses the almost-sure satisfaction of the extension axioms and a back-and-forth / Ehrenfeucht-Fraïssé argument.

Estimated time

beginner: 17m
intermediate: 46m
master: 85m