small subgraph counts and the second-moment method

A basic family of questions about a random graph is: when does it contain a copy of a fixed small graph H — a triangle, a 4-cycle, a complete graph K_4, a path? The answer comes from controlling the random variable X = (number of copies of H in G(n,p)) via its first two moments. This pairing — the first-moment method to show a property fails, the second-moment method to show it holds — is the workhorse technique of the field and the cleanest illustration of the probabilistic method. The question it answers is: at what density does a given local structure appear, and why exactly there?

The first-moment method is Markov's inequality: P(X >= 1) <= E[X], so if E[X] tends to 0 then whp X = 0 (no copy of H). The expected number of copies is E[X] = (number of ways to place H) times p^(e_H), which scales like n^(v_H) p^(e_H) where v_H, e_H are the vertices and edges of H. This tends to 0 below the threshold p* = n^(-v_H/e_H) — but the true threshold is governed not by H itself but by its densest subgraph: define the maximum density m(H) = max over subgraphs F of (e_F / v_F), then the threshold is p* = n^(-1/m(H)). The reason is that a sparse H can appear only once its densest part has appeared. To prove copies DO appear above the threshold one cannot use the first moment (large mean does not imply X >= 1); one uses the second-moment method, the Paley-Zygmund / Chebyshev bound P(X = 0) <= Var(X)/E[X]^2. One computes Var(X) by summing the covariances of pairs of potential copies over how many vertices they share; if E[X] tends to infinity and the variance is of smaller order than E[X]^2 (which holds when the overlap terms are controlled, i.e. for so-called balanced H), then X/E[X] tends to 1 and in particular X >= 1 whp.

These two moments together locate the appearance threshold of every fixed subgraph and, with the Stein-Chen refinement, even give the Poisson limit law for the count right at the threshold. The technique reaches far beyond graphs: it is how one proves existence of combinatorial objects (Ramsey graphs, designs), lower bounds on the chromatic number, and concentration of counts. The honesty to keep: the second-moment method needs the variance to be genuinely small relative to the squared mean, which can FAIL when H is unbalanced (a subgraph denser than the whole) — then E[X] can tend to infinity while X is still 0 whp, because the count is dominated by rare clustered configurations. This is exactly why the threshold is set by m(H), the densest subgraph, not by H's overall density; getting this wrong is the classic mistake.