塞邁雷迪正則性引理

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

定義和引理敍述

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

密度

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

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

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

ε-正則

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

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

ε-正則劃分

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

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

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

正則性引理

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

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

推廣

János Komlós（英語：János Komlós）、Gábor Sárközy（英語：Gábor Sárközy）和塞邁雷迪·安德烈其後（於 1997 年）證明了blow-up 引理^[9]^[10] ，其斷言塞邁雷迪正則性引理中的正則對，在特定意義下與完全二部圖具有同樣的性質。若考慮將大而疏的圖，嵌入到一個稠密的圖中，則適用 blow-up 引理來深入研究該嵌入的性質。

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

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

參考文獻

^ Szemerédi, Endre, On sets of integers containing no k elements in arithmetic progression, Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica, 1975, 27: 199–245 [2018-12-02], MR 0369312, （原始內容存檔於2012-02-05） .
^ Szemerédi, Endre, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS 260, Paris: CNRS: 399–401, 1978, MR 0540024 .
^ Frankl, Peter; Rödl, Vojtěch, Extremal problems on set systems, Random Structures & Algorithms, 2002, 20 (2): 131–164, MR 1884430, doi:10.1002/rsa.10017.abs .
^ Rödl, Vojtěch; Skokan, Jozef, Regularity lemma for $k$ -uniform hypergraphs, Random Structures & Algorithms, 2004, 25 (1): 1–42, MR 2069663, doi:10.1002/rsa.20017 .
^ Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias, The counting lemma for regular $k$ -uniform hypergraphs, Random Structures & Algorithms, 2006, 28 (2): 113–179, MR 2198495, doi:10.1002/rsa.20117 .
^ Gowers, W. T., Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combinatorics, Probability and Computing, 2006, 15 (1-2): 143–184, MR 2195580, doi:10.1017/S0963548305007236 .
^ Gowers, W. T., Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, Second Series, 2007, 166 (3): 897–946, MR 2373376, arXiv:0710.3032 , doi:10.4007/annals.2007.166.897 .
^ Gowers, W. T., Lower bounds of tower type for Szemerédi's uniformity lemma, Geometric and Functional Analysis, 1997, 7 (2): 322–337, MR 1445389, doi:10.1007/PL00001621 .
^ Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre, Blow-up lemma, Combinatorica, 1997, 17 (1): 109–123, MR 1466579, doi:10.1007/BF01196135
^ Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre, An algorithmic version of the blow-up lemma, Random Structures & Algorithms, 1998, 12 (3): 297–312, MR 1635264, arXiv:math/9612213 , doi:10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W
^ Tao, Terence, Szemerédi's regularity lemma revisited, Contributions to Discrete Mathematics, 2006, 1 (1): 8–28, Bibcode:2005math......4472T, MR 2212136, arXiv:math/0504472  .
^ Conlon, David; Fox, Jacob, Bounds for graph regularity and removal lemmas, Geometric and Functional Analysis, 2012, 22 (5): 1191–1256, MR 2989432, arXiv:1107.4829 , doi:10.1007/s00039-012-0171-x

參見

Komlós, J.; Simonovits, M., Szemerédi's regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest: 295–352, 1996, MR 1395865 .
Komlós, J.; Shokoufandeh, Ali; Simonovits, Miklós; Szemerédi, Endre, The regularity lemma and its applications in graph theory, Theoretical aspects of computer science (Tehran, 2000), Lecture Notes in Computer Science 2292, Springer, Berlin: 84–112, 2002, MR 1966181, doi:10.1007/3-540-45878-6_3 .

[1] Szemerédi, Endre, On sets of integers containing no k elements in arithmetic progression, Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica, 1975, 27: 199–245 [2018-12-02], MR 0369312, （原始內容存檔於2012-02-05） .

[2] Szemerédi, Endre, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS 260, Paris: CNRS: 399–401, 1978, MR 0540024 .

[3] Frankl, Peter; Rödl, Vojtěch, Extremal problems on set systems, Random Structures & Algorithms, 2002, 20 (2): 131–164, MR 1884430, doi:10.1002/rsa.10017.abs .

[4] Rödl, Vojtěch; Skokan, Jozef, Regularity lemma for $k$ -uniform hypergraphs, Random Structures & Algorithms, 2004, 25 (1): 1–42, MR 2069663, doi:10.1002/rsa.20017 .

[5] Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias, The counting lemma for regular $k$ -uniform hypergraphs, Random Structures & Algorithms, 2006, 28 (2): 113–179, MR 2198495, doi:10.1002/rsa.20117 .

[6] Gowers, W. T., Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combinatorics, Probability and Computing, 2006, 15 (1-2): 143–184, MR 2195580, doi:10.1017/S0963548305007236 .

[7] Gowers, W. T., Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, Second Series, 2007, 166 (3): 897–946, MR 2373376, arXiv:0710.3032 , doi:10.4007/annals.2007.166.897 .

[8] Gowers, W. T., Lower bounds of tower type for Szemerédi's uniformity lemma, Geometric and Functional Analysis, 1997, 7 (2): 322–337, MR 1445389, doi:10.1007/PL00001621 .

[9] Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre, Blow-up lemma, Combinatorica, 1997, 17 (1): 109–123, MR 1466579, doi:10.1007/BF01196135

[10] Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre, An algorithmic version of the blow-up lemma, Random Structures & Algorithms, 1998, 12 (3): 297–312, MR 1635264, arXiv:math/9612213 , doi:10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W

[11] Tao, Terence, Szemerédi's regularity lemma revisited, Contributions to Discrete Mathematics, 2006, 1 (1): 8–28, Bibcode:2005math......4472T, MR 2212136, arXiv:math/0504472  .

[12] Conlon, David; Fox, Jacob, Bounds for graph regularity and removal lemmas, Geometric and Functional Analysis, 2012, 22 (5): 1191–1256, MR 2989432, arXiv:1107.4829 , doi:10.1007/s00039-012-0171-x

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]