数学上，塞迈雷迪正则性引理（Szemerédi regularity lemma）断言，给定任意一个足够大的图，都可以将其顶点集划分成若干个差不多一样大的子集，使得几乎每两个不同的子集之间的边，都具有随机二部图的性质。塞迈雷迪于 1975 年引入了该引理较弱的版本，其只适用于二部图，用作证明塞迈雷迪定理，后来再于 1978 年证明了完整的版本。 Vojtěch Rödl（英语：Vojtěch Rödl） 及其合作者和高尔斯将正则性方法推广到超图上。
塞迈雷迪正则性引理的严格叙述须用到下列定义。设 为一幅图，而 为其顶点集。
设 , 为 的两个互斥子集。定义 (, ) 的密度为
其中 (, ) 为一个顶点在 中，而另一个顶点在 中的边的集合。
对于 > 0, 称两个由顶点组成的集合 和 为 -正则，若对任意满足|| ≥ || 和 || ≥ || 的子集 ⊆ 和 ⊆ , 都有
设 1, ..., 为将 分成 份的划分。其称为 -正则划分，若：
利用上述定义，可以写出引理的严格叙述。
对任意的 > 0 和正整数 , 存在整数 , 其满足：若 为至少有 个顶点的图，则存在整数 满足 ≤ ≤ , 和一个 -正则划分将 的顶点集分成 份。
引理的证明所给出的 的上界极大，比如 的 O(−5) 次迭代幂次。若实际的上界并非如此大，而是 exp( -) 的形式的话，则其可应用在其他地方。然而，高尔斯于 1997 年找到了一些图作为例子，证明 确实可以增长得极快，比如至少为 的 −1/16 次迭代幂次。由此可见，最佳的上界必定位于 Grzegorczyk 分层（英语：Grzegorczyk hierarchy）中的第 4 层，因此不属初等递归函数。
János Komlós（英语：János Komlós）、Gábor Sárközy（英语：Gábor Sárközy）和塞迈雷迪·安德烈其后（于 1997 年）证明了blow-up 引理 ，其断言塞迈雷迪正则性引理中的正则对，在特定意义下与完全二部图具有同样的性质。若考虑将大而疏的图，嵌入到一个稠密的图中，则适用 blow-up 引理来深入研究该嵌入的性质。
陶哲轩以概率方法证明了一条不等式，其推广了塞迈雷迪正则性引理。
注意，不可能在塞迈雷迪正则性引理中，证明“所有”对都正则。原因是，一些图（比如半图（英语：Half graph））确实需要划分中有若干对顶点集非正则，尽管按照正则性引理，这样的对只占很小一部分。
