Szemerédi's regularity lemma

For disjoint sets A and B, their pair density is the number of crossing edges divided by the product of their sizes. The pair is epsilon-regular if every pair of subsets A-prime and B-prime, each containing at least an epsilon fraction of its parent set, has density within epsilon of the original density. Both the threshold and the allowed error use the same parameter. Tiny exceptional subsets can behave differently without violating this definition.

A pair can have density one half and still fail regularity badly. Divide both sides into equal halves and put in all edges between corresponding halves, with no other crossing edges. The whole density is one half, but a corresponding-half pair has density one. For epsilon less than one half, these large witnesses expose the discrepancy. Thus a single pair-density number loses information that the regularity condition is designed to control. Regularity also does not require every individual vertex to have the average degree.

For every epsilon between zero and one and every positive integer m-zero, there are integers M and n-zero such that every graph with at least n-zero vertices admits a partition into an exceptional class V-zero and k ordinary classes. The ordinary classes have equal size, the exceptional class contains at most epsilon n vertices, and m-zero is at most k, which is at most M. At most epsilon k squared unordered pairs of distinct ordinary classes are irregular. This particular numerical convention counts unordered pairs, so the bound need not be an epsilon fraction of all such pairs.

The key quantifier is that M is chosen independently of the eventual graph order and its individual edges. A partition depending on the particular graph is allowed. There is no promise that its parts are independent sets or that all pairs are regular. To use the theorem for embedding a fixed pattern, one must choose epsilon small compared with the density threshold and the pattern's size before applying it. Choosing a coarse epsilon first and hoping every later counting lemma accepts it reverses the required dependence.

A partition has an energy obtained by averaging the squared densities of its block pairs, weighted by their relative sizes. Refining a block replaces its density by a weighted average of finer densities; convexity says the weighted square average cannot decrease. An irregular pair provides witness subsets with a definite density discrepancy, and splitting along those witnesses produces a definite energy gain. If sufficiently many pairs are irregular, the total gain is bounded below by a positive function of epsilon.

Energy stays between zero and one, so only boundedly many substantial increments are possible. Refining simultaneously for many witnesses can multiply the number of parts dramatically; equalizing the part sizes and managing exceptional vertices require additional bookkeeping. This is the proof mechanism, not a complete proof of the lemma. It explains both the independence from n and why the theoretical partition bound is too large for many direct numerical applications. More efficient weak-regularity variants give different guarantees and should not be substituted without checking the counting task.