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$ 条边；只说“忽略坏对”而不给损失上界，无法支撑移除或稳定性结论。