塞邁雷迪正則性引理

設 X, Y 為 V 的兩個互斥子集。定義 (X, Y) 的密度為

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

其中 E(X, Y) 為一個頂點在 X 中，而另一個頂點在 Y 中的邊的集合。

對於 ε > 0, 稱兩個由頂點組成的集合 X 和 Y 為 ε-正則，若對任意滿足|A| ≥ ε|X| 和 |B| ≥ ε|Y| 的子集 A ⊆ X 和 B ⊆ Y, 都有

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon .}$

設 V₁, ...,  V_k 為將 V 分成 k 份的劃分。其稱為 ε-正則劃分，若：

• 對每個 i, j 都有 V_i 與 V_j 的大小至多相差 1.
• 除了至多 εk² 對滿足 i < j 的 V_i, V_j 以外，其他的每一對都 ε-正則。

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

對任意的 ε > 0 和正整數 m, 存在整數 M, 其滿足：若 G 為至少有 M 個頂點的圖，則存在整數 k 滿足 m ≤ k ≤ M, 和一個 ε-正則劃分將 G 的頂點集分成 k 份。

引理的證明所給出的 M 的上界極大，比如 m 的 O(ε⁻⁵) 次迭代冪次。若實際的上界並非如此大，而是 exp(ε ^-β) 的形式的話，則其可應用在其他地方。然而，高爾斯於 1997 年找到了一些圖作為例子，證明 M 確實可以增長得極快，比如至少為 m 的 ε^−1/16 次疊代冪次。由此可見，最佳的上界必定位於 Grzegorczyk 分層中的第 4 層，因此不屬初等遞歸函數[8]。