數學上,塞邁雷迪正則性引理(Szemerédi regularity lemma)斷言,給定任意一個足夠大的圖,都可以將其頂點集劃分成若干個差不多一樣大的子集,使得幾乎每兩個不同的子集之間的邊,都具有隨機二部圖的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本,其只適用於二部圖,用作證明塞邁雷迪定理[1],後來再於 1978 年證明了完整的版本[2]。 Vojtěch Rödl 及其合作者[3][4][5]和高爾斯[6][7]將正則性方法推廣到超圖上。
定義和引理敍述
設 X, Y 為 V 的兩個互斥子集。定義 (X, Y) 的密度為
其中 E(X, Y) 為一個頂點在 X 中,而另一個頂點在 Y 中的邊的集合。
對於 ε > 0, 稱兩個由頂點組成的集合 X 和 Y 為 ε-正則,若對任意滿足|A| ≥ ε|X| 和 |B| ≥ ε|Y| 的子集 A ⊆ X 和 B ⊆ Y, 都有
設 V1, ..., Vk 為將 V 分成 k 份的劃分。其稱為 ε-正則劃分,若:
- 對每個 i, j 都有 Vi 與 Vj 的大小至多相差 1.
- 除了至多 εk2 對滿足 i < j 的 Vi, Vj 以外,其他的每一對都 ε-正則。
利用上述定義,可以寫出引理的嚴格敍述。
對任意的 ε > 0 和正整數 m, 存在整數 M, 其滿足:若 G 為至少有 M 個頂點的圖,則存在整數 k 滿足 m ≤ k ≤ M, 和一個 ε-正則劃分將 G 的頂點集分成 k 份。
引理的證明所給出的 M 的上界極大,比如 m 的 O(ε−5) 次迭代冪次。若實際的上界並非如此大,而是 exp(ε -β) 的形式的話,則其可應用在其他地方。然而,高爾斯於 1997 年找到了一些圖作為例子,證明 M 確實可以增長得極快,比如至少為 m 的 ε−1/16 次疊代冪次。由此可見,最佳的上界必定位於 Grzegorczyk 分層中的第 4 層,因此不屬初等遞歸函數[8]。
推廣
János Komlós、Gábor Sárközy和塞邁雷迪·安德烈其後(於 1997 年)證明了blow-up 引理[9][10] ,其斷言塞邁雷迪正則性引理中的正則對,在特定意義下與完全二部圖具有同樣的性質。若考慮將大而疏的圖,嵌入到一個稠密的圖中,則適用 blow-up 引理來深入研究該嵌入的性質。
陶哲軒以概率方法證明了一條不等式,其推廣了塞邁雷迪正則性引理[11]。
注意,不可能在塞邁雷迪正則性引理中,證明「所有」對都正則。原因是,一些圖(比如半圖)確實需要劃分中有若干對頂點集非正則,儘管按照正則性引理,這樣的對只佔很小一部分。[12]
參考文獻
參見
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.