Supersaturation and counting subgraphs

Fix a graph H with h vertices and at least one edge, and fix a positive real number epsilon. Supersaturation states that there are positive constants c and n-zero, depending on H and epsilon, such that every n-vertex graph with n at least n-zero and at least ex(n,H) plus epsilon times n squared edges contains at least c times n to the h copies of H. The constants are chosen before seeing the particular large graph. If the edge hypothesis is impossible, the implication is simply vacuous.

For a fixed clique, one can instead use a fixed positive density excess over its limiting Turán density. The two forms agree asymptotically after adjusting constants, but they should not be conflated in a finite calculation. If epsilon is allowed to shrink with n, the theorem does not supply a uniform constant c. Adding a single edge to a balanced complete bipartite graph creates only linearly many triangles, so it cannot justify a positive constant fraction of n cubed triangles.

The proof mechanism samples a fixed-size vertex subset. With its size chosen sufficiently large using H and epsilon, the expected number of sampled edges remains above the relevant small-graph threshold by a controlled margin. Since no sample can have arbitrarily many edges, a positive proportion of samples must actually cross that threshold. Each such sample contains H. This is a proof sketch: choosing the sample size rigorously uses convergence of normalized extremal numbers and must precede sending the host order to infinity.

Now count pairs consisting of a sampled vertex set and a copy of H lying inside it. A fixed copy occurs in exactly the binomial number of samples obtained by adding the remaining sample vertices outside that copy. Dividing the lower bound for witness-containing samples by this upper multiplicity gives a constant times n to the h copies. The argument needs no assumption that copies are edge-disjoint. Heavy overlap is permitted; the multiplicity calculation is what prevents overlap from invalidating the count.

An injective labeled embedding specifies where each named vertex of H goes. Each unlabelled copy gives exactly the number of automorphisms of H such embeddings. For a triangle that factor is six. Homomorphisms allow collisions between nonadjacent source vertices, so they are another count; for a fixed simple H, noninjective maps contribute at most a constant times n to the h minus one. That lower-order difference matters in exact finite examples but disappears after normalizing by n to the h.

Density alone does not guarantee the random-graph count for every pattern. A complete balanced bipartite graph has many edges and zero triangles, whereas an independent-edge model at similar edge density has many expected triangles. Supersaturation concerns crossing a forbidden-pattern threshold, not asserting independence. Later regularity and graphon methods explain which additional structural information controls counts. For now, state both the pattern being counted and the convention, then verify that every normalization in a proof uses those same choices.