the second moment method
The second moment method is the tool that upgrades the one-sided first moment method into a two-sided statement: it proves that a non-negative counting random variable is not just large in expectation but actually positive — and often concentrated near its mean — with high probability. It is the standard route to lower bounds for thresholds in random graphs and to showing that a desired substructure typically exists rather than merely existing on average. Where the first moment shows P(X = 0) is small when E[X] is small, the second moment shows P(X = 0) is small when E[X] is large, provided the variance is well controlled.
The engine is Chebyshev's inequality applied to a count X. The cleanest consequence is the bound P(X = 0) <= Var(X) / (E[X])^2. So if the variance is of smaller order than the square of the mean — that is, Var(X) = o((E[X])^2) — then P(X = 0) -> 0 and X is positive with probability tending to 1; in fact X concentrates: X / E[X] -> 1 in probability. The whole task reduces to estimating the variance. Writing X = sum of indicator variables for the substructures, Var(X) = sum of covariances, and the dominant terms come from pairs of substructures that overlap (share vertices or edges). When the overlapping pairs contribute negligibly compared to E[X]^2, the variance is controlled and existence follows.
This is exactly how one nails the location of thresholds. For a monotone property, the first moment gives the lower side (below the threshold the expected count vanishes, so the property fails) and the second moment gives the upper side (above the threshold the count is concentrated and positive, so the property holds). The classic application is the appearance of a fixed subgraph H in G(n,p): a careful variance computation shows that the threshold is governed by the densest subgraph of H. The honest caveat is that the second moment can fail when a few atypical configurations inflate the variance; in those cases one truncates, conditions, or upgrades to Janson's inequality, which gives exponential rather than merely polynomial control of the lower tail.
Threshold for a triangle in G(n,p). Let X count triangles, E[X] ~ (np)^3/6. The variance is dominated by pairs of triangles sharing an edge, contributing ~ n^4 p^5. Then Var(X)/E[X]^2 ~ (n^4 p^5)/(n^6 p^6) = 1/(n^2 p) plus 1/E[X]. Both -> 0 exactly when np -> infinity, so for p >> 1/n the graph contains a triangle with probability tending to 1 — matching the first-moment lower bound and pinning the threshold at p ~ 1/n.
Var(X) = o(E[X]^2) forces X > 0 (and concentration) via P(X=0) <= Var(X)/E[X]^2.
The bound P(X=0) <= Var(X)/E[X]^2 can be weak when rare high-value configurations dominate the variance; then Janson's inequality (exponential lower-tail control) or truncation is needed instead.