Szemerédi 正则性引理

正则对并非逐边随机，而是说任何达到可见尺度的大块，都看到几乎同样的边密度。把每个簇压成一个点、把密度足够高的正则簇对压成一条边，就得到规模有界的约化图；许多稠密图问题于是先在约化图上解决，再把结构提升回原图。

证明以能量增量为发动机。对一个划分定义均方密度指标

它始终有界。若有太多不正则簇对，定义就为每一对提供见证子集 $A^{\prime },B^{\prime }$；按这些见证同时细分各簇，可使能量增加至少一个只依赖 $\epsilon$ 的正量，典型估计为 $\mathrm{\Omega }({\epsilon }^5)$。能量不能无限增加，所以有限轮后终止。代价是每轮部数可能指数爆炸，最终 $M$ 通常呈塔式增长。

令 $A=A_1\bigsqcup A_2$、$B=B_1\bigsqcup B_2$，四个小块大小都为 $2$；只连接 $A_1$ 与 $B_1$ 之间、以及 $A_2$ 与 $B_2$ 之间的全部边。整体有 $8$ 条边，故 $d(A,B)=1/2$。但取 $A^{\prime }=A_1,B^{\prime }=B_1$，得到 $d(A^{\prime },B^{\prime })=1$。由于 $|A^{\prime }|=|A|/2$、$|B^{\prime }|=|B|/2$，这对顶点集不是 $0.4$-正则的：密度偏差 $1/2$ 大于 $0.4$。总体密度看似均匀，块结构却被大子集立即识破。

相反，密度为 $0$ 或 $1$ 的簇对对每个 $\epsilon$ 都正则，因为所有大子对密度完全相同。正则性不等于密度接近 $1/2$；“均匀”描述的是跨尺度稳定，而不是边与非边等量。

引理允许 $\epsilon k^2$ 个坏簇对和 $\epsilon n$ 个异常顶点，不能声称所有顶点或所有簇对都表现随机。它是稠密图工具：当 $e(G)=o(n^2)$ 时，许多簇对密度都趋零，普通正则性可能只给出空洞近似；稀疏图需要相对密度、上正则性或伪随机性等附加条件。

塔式参数还意味着引理主要是结构与存在性工具。即使固定 $\epsilon$ 时有算法版本，直接生成的划分也可能过大，不应把“部数只依赖 $\epsilon$”误读成实践中很小。

图计数引理理路图计数引理Graph counting lemma · Counting lemma for regular pairs · 正则对计数引理固定小图的各条边落在正则簇对上时，其跨簇副本密度与边密度乘积之间的加性误差由正则参数控制。说明约化图中的固定小图在原图中产生大量副本；二者合用可证明图移除引理理路图移除引理Graph removal lemma · H-removal lemma · 图删除引理固定图的副本数若低于正确幂次的足够小比例，就能删除少量边消灭全部该图副本。与 Erdős–Stone 定理。正则划分也用于近似同态、稠密图极限和性质测试，因为它把任意大图压缩成有限密度矩阵，同时控制固定大小子图统计。

使用时通常先删除异常集、非正则对和密度过低的正则对，再研究剩余约化图。每类删除都必须单独记账，确保总共不超过目标的 $\epsilon n^2$ 条边；只说“忽略坏对”而不给损失上界，无法支撑移除或稳定性结论。