塞邁雷迪正則性引理

Szemerédi 正規引理的圖示

數學上，塞邁雷迪正則性引理（Szemerédi regularity lemma）斷言，給定任意一個足夠大的圖，都可以將其頂點集劃分成若干個差不多一樣大的子集，使得幾乎每兩個不同的子集之間的邊，都具有隨機二部圖的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本，其只適用於二部圖，用作證明塞邁雷迪定理，後來再於 1978 年證明了完整的版本。 Template:Link-en 及其合作者和高爾斯將正則性方法推廣到超圖上。

定義和引理敍述

塞邁雷迪正則性引理的嚴格敍述須用到下列定義。設 Template:Math 為一幅圖，而 Template:Math 為其頂點集。

密度

設 Template:Math 為 Template:Math 的兩個互斥子集。定義 Template:Math 的密度為

$d(X,Y):=\frac{|E(X,Y)|}{|X||Y|},$

其中 Template:Math 為一個頂點在 Template:Math 中，而另一個頂點在 Template:Math 中的邊的集合。

ε-正則

對於 Template:Math, 稱兩個由頂點組成的集合 Template:Math 和 Template:Math 為 Template:Math-正則，若對任意滿足Template:Math 和 Template:Math 的子集 Template:Math 和 Template:Math, 都有

$|d(X,Y)-d(A,B)|\le \epsilon .$

ε-正則劃分

設 Template:Math 為將 Template:Math 分成 Template:Math 份的劃分。其稱為 Template:Math-正則劃分，若：

• 對每個 Template:Math 都有 Template:Math 與 Template:Math 的大小至多相差 1.
• 除了至多 Template:Math 對滿足 Template:Math 的 Template:Math, Template:Math 以外，其他的每一對都 Template:Math-正則。

利用上述定義，可以寫出引理的嚴格敍述。

正則性引理

對任意的 Template:Math 和正整數 Template:Math, 存在整數 Template:Math, 其滿足：若 Template:Math 為至少有 Template:Math 個頂點的圖，則存在整數 Template:Math 滿足 Template:Math, 和一個 Template:Math-正則劃分將 Template:Math 的頂點集分成 Template:Math 份。

引理的證明所給出的 Template:Math 的上界極大，比如 Template:Math 的 Template:Math 次迭代冪次。若實際的上界並非如此大，而是 Template:Math 的形式的話，則其可應用在其他地方。然而，高爾斯於 1997 年找到了一些圖作為例子，證明 Template:Math 確實可以增長得極快，比如至少為 Template:Math 的 Template:Math 次疊代冪次。由此可見，最佳的上界必定位於 Template:Link-en中的第 4 層，因此不屬初等遞歸函數。

推廣

Template:Link-en、Template:Link-en和塞迈雷迪·安德烈其後（於 1997 年）證明了blow-up 引理 ，其斷言塞邁雷迪正則性引理中的正則對，在特定意義下與完全二部圖具有同樣的性質。若考慮將大而疏的圖，嵌入到一個稠密的圖中，則適用 blow-up 引理來深入研究該嵌入的性質。

陶哲軒以概率方法證明了一條不等式，其推廣了塞邁雷迪正則性引理。

注意，不可能在塞邁雷迪正則性引理中，證明「所有」對都正則。原因是，一些圖（比如Template:Link-en）確實需要劃分中有若干對頂點集非正則，儘管按照正則性引理，這樣的對只佔很小一部分。

參見

• Template:Citation.
• Template:Citation.