查看“︁塞邁雷迪正則性引理”︁的源代码

[[File:Epsilon regular partition.png|thumb|Szemerédi 正規引理的圖示]]
[[數學]]上，'''[[塞迈雷迪·安德烈|塞邁雷迪]]正則性引理'''（Szemerédi regularity lemma）斷言，給定任意一個足夠大的[[图 (数学)|圖]]，都可以將其頂點集劃分成若干個差不多一樣大的子集，使得幾乎每兩個不同的子集之間的邊，都具有隨機[[二部圖]]的性質。塞邁雷迪於 1975 年引入了該引理較弱的版本，其只適用於二部圖，用作證明[[塞邁雷迪定理]]<ref>{{Citation | last1=Szemerédi | first1=Endre | author1-link=塞迈雷迪·安德烈 | title=On sets of integers containing no k elements in arithmetic progression | url=http://matwbn.icm.edu.pl/tresc.php?wyd=6&tom=27 | mr=0369312 | year=1975 | journal=Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica | volume=27 | pages=199–245 | access-date=2018-12-02 | archive-url=https://web.archive.org/web/20120205024747/http://matwbn.icm.edu.pl/tresc.php?wyd=6&tom=27 | archive-date=2012-02-05 | dead-url=no }}.</ref>，後來再於 1978 年證明了完整的版本<ref>{{Citation | last1=Szemerédi | first1=Endre | author1-link=塞迈雷迪·安德烈 | title=Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) | publisher=CNRS | location=Paris | series=Colloq. Internat. CNRS | mr=540024 | year=1978 | volume=260 | chapter=Regular partitions of graphs | pages=399–401}}.</ref>。 
{{Link-en|Vojtěch Rödl}} 及其合作者<ref>{{citation
 | last1 = Frankl | first1 = Peter 
 | last2 = Rödl | first2 = Vojtěch 
 | doi = 10.1002/rsa.10017.abs
 | issue = 2
 | journal = Random Structures & Algorithms
 | mr = 1884430
 | pages = 131–164
 | title = Extremal problems on set systems
 | volume = 20
 | year = 2002}}.</ref><ref>{{citation
 | last1 = Rödl | first1 = Vojtěch 
 | last2 = Skokan | first2 = Jozef
 | doi = 10.1002/rsa.20017
 | issue = 1
 | journal = Random Structures & Algorithms
 | mr = 2069663
 | pages = 1–42
 | title = Regularity lemma for {{mvar|k}}-uniform hypergraphs
 | volume = 25
 | year = 2004}}.</ref><ref>{{citation
 | last1 = Nagle | first1 = Brendan
 | last2 = Rödl | first2 = Vojtěch 
 | last3 = Schacht | first3 = Mathias  | doi = 10.1002/rsa.20117
 | issue = 2
 | journal = Random Structures & Algorithms
 | mr = 2198495
 | pages = 113–179
 | title = The counting lemma for regular {{mvar|k}}-uniform hypergraphs
 | volume = 28
 | year = 2006}}.</ref>和[[蒂莫西·高爾斯|高爾斯]]<ref>{{citation
 | last = Gowers | first = W. T. | authorlink = Timothy Gowers
 | doi = 10.1017/S0963548305007236
 | issue = 1-2
 | journal = Combinatorics, Probability and Computing
 | mr = 2195580
 | pages = 143–184
 | title = Quasirandomness, counting and regularity for 3-uniform hypergraphs
 | volume = 15
 | year = 2006}}.</ref><ref>{{citation
 | last = Gowers | first = W. T. | authorlink = Timothy Gowers
 | doi = 10.4007/annals.2007.166.897
 | issue = 3
 | journal = [[数学年刊|Annals of Mathematics]]
 | mr = 2373376
 | pages = 897–946
 | series = Second Series
 | title = Hypergraph regularity and the multidimensional Szemerédi theorem
 | volume = 166
 | year = 2007| arxiv = 0710.3032
 }}.</ref>將正則性方法推廣到[[超圖]]上。

==定義和引理敍述==
塞邁雷迪正則性[[引理]]的嚴格敍述須用到下列定義。設 {{math|''G''}} 為一幅圖，而 {{math|''V''}} 為其[[顶点 (图论)|頂點]]集。

===密度===
設 {{math|''X'',&nbsp;''Y''}} 為 {{math|''V''}} 的兩個互斥子集。定義 {{math|(''X'',&nbsp;''Y'')}} 的'''密度'''為

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

其中 {{math|''E''(''X'',&nbsp;''Y'')}} 為一個頂點在 {{math|''X''}} 中，而另一個頂點在 {{math|''Y''}} 中的邊的集合。

===''ε''-正則===
對於 {{math|''ε''&nbsp;>&nbsp;0}}, 稱兩個由頂點組成的集合 {{math|''X''}} 和 {{math|''Y''}} 為 '''{{math|''ε''}}-正則'''，若對任意滿足{{math|<nowiki>|</nowiki>''A''<nowiki>|</nowiki>&nbsp;≥&nbsp;''ε''<nowiki>|</nowiki>''X''<nowiki>|</nowiki>}} 和 {{math|<nowiki>|</nowiki>''B''<nowiki>|</nowiki>&nbsp;≥&nbsp;''ε''<nowiki>|</nowiki>''Y''<nowiki>|</nowiki>}} 的子集 {{math|''A''&nbsp;⊆&nbsp;''X''}} 和 {{math|''B''&nbsp;⊆&nbsp;''Y''}}, 都有

:<math>\left| d(X,Y) - d(A,B) \right| \le \varepsilon.</math>

===''ε''-正則劃分===
設 {{math|''V''<sub>1</sub>,&nbsp;...,&nbsp; ''V<sub>k</sub>''}} 為將 {{math|''V''}} 分成 {{math|''k''}} 份的[[集合划分|劃分]]。其稱為 '''{{math|''ε''}}-正則劃分'''，若： 
*對每個 {{math|''i'',&nbsp;''j''}} 都有 {{math|''V<sub>i</sub>''}} 與 {{math|''V<sub>j</sub>''}} 的大小至多相差 1. 
*除了至多 {{math|''εk''<sup>2</sup>}} 對滿足 {{math|''i''&nbsp;<&nbsp;''j''}} 的 {{math|''V<sub>i</sub>''}}, {{math|''V<sub>j</sub>''}} 以外，其他的每一對都 {{math|''ε''}}-正則。

利用上述定義，可以寫出引理的嚴格敍述。
===正則性引理===
對任意的 {{math|''ε''&nbsp;>&nbsp;0}} 和[[正整數]] {{math|''m''}}, 存在整數 {{math|''M''}}, 其滿足：若 {{math|''G''}} 為至少有 {{math|''M''}} 個頂點的圖，則存在整數 {{math|''k''}} 滿足 {{math|''m''&nbsp;&le;&nbsp;''k''&nbsp;&le;&nbsp;''M''}}, 和一個 {{math|''ε''}}-正則劃分將 {{math|''G''}} 的頂點集分成 {{math|''k''}} 份。

引理的證明所給出的 {{math|''M''}} 的上界極大，比如 {{math|''m''}} 的 {{math|[[大O符号|O]](''ε''<sup>−5</sup>)}} 次[[迭代冪次]]。若實際的上界並非如此大，而是 {{Math|exp(''ε''<sup> -''β''</sup>)}} 的形式的話，則其可應用在其他地方。然而，高爾斯於 1997 年找到了一些圖作為例子，證明 {{math|''M''}} 確實可以增長得極快，比如至少為 {{math|''m''}} 的 {{math|''ε''<sup>−1/16</sup>}} 次疊代冪次。由此可見，最佳的上界必定位於 {{Link-en|Grzegorczyk 分層|Grzegorczyk hierarchy}}中的第 4 層，因此不屬[[ELEMENTARY|初等遞歸函數]]<ref>{{citation
 | last = Gowers | first = W. T. | authorlink = Timothy Gowers
 | doi = 10.1007/PL00001621
 | issue = 2
 | journal = Geometric and Functional Analysis
 | mr = 1445389
 | pages = 322–337
 | title = Lower bounds of tower type for Szemerédi's uniformity lemma
 | volume = 7
 | year = 1997}}.</ref>。

== 推廣 ==
{{Link-en|János Komlós}}、{{Link-en|Gábor Sárközy}}和[[塞迈雷迪·安德烈]]其後（於 1997 年）證明了[[blow-up 引理]]<ref>{{citation
 | last1 = Komlós | first1 = János 
 | last2 = Sárközy | first2 = Gábor N. 
 | last3 = Szemerédi | first3 = Endre | author3-link = 塞迈雷迪·安德烈
 | doi = 10.1007/BF01196135
 | issue = 1
 | journal = Combinatorica
 | mr = 1466579
 | pages = 109–123
 | title = Blow-up lemma
 | volume = 17
 | year = 1997}}</ref><ref>{{citation
 | last1 = Komlós | first1 = János 
 | last2 = Sárközy | first2 = Gábor N. 
 | last3 = Szemerédi | first3 = Endre | author3-link = 塞迈雷迪·安德烈
 | doi = 10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W
 | issue = 3
 | journal = Random Structures & Algorithms
 | mr = 1635264
 | pages = 297–312
 | title = An algorithmic version of the blow-up lemma
 | volume = 12
 | year = 1998| arxiv = math/9612213}}</ref> ，其斷言塞邁雷迪正則性引理中的正則對，在特定意義下與[[完全二部图|完全二部圖]]具有同樣的性質。若考慮將大而疏的圖，[[嵌入 (数学)|嵌入]]到一個稠密的圖中，則適用 blow-up 引理來深入研究該嵌入的性質。

[[陶哲軒]]以概率方法證明了一條不等式，其推廣了塞邁雷迪正則性引理<ref>{{citation
 | last = Tao | first = Terence | authorlink = 陶哲轩
 | arxiv = math/0504472
 | issue = 1
 | journal = Contributions to Discrete Mathematics
 | mr = 2212136
 | pages = 8–28
 | title = Szemerédi's regularity lemma revisited
 | volume = 1
 | year = 2006| bibcode = 2005math......4472T}}.</ref>。

注意，不可能在塞邁雷迪正則性引理中，證明「所有」對都正則。原因是，一些圖（比如{{Link-en|半圖|Half graph}}）確實需要劃分中有若干對頂點集非正則，儘管按照正則性引理，這樣的對只佔很小一部分。<ref>{{citation
 | last1 = Conlon | first1 = David 
 | last2 = Fox | first2 = Jacob 
 | arxiv = 1107.4829
 | doi = 10.1007/s00039-012-0171-x
 | issue = 5
 | journal = Geometric and Functional Analysis
 | mr = 2989432
 | pages = 1191–1256
 | title = Bounds for graph regularity and removal lemmas
 | volume = 22
 | year = 2012}}</ref>
<!-- 或許可考慮加入 en: Algorithmic version for Szemerédi regularity partition 中提及的證明-->

==參考文獻==
{{reflist}}

==參見==
*{{citation
 | last1 = Komlós | first1 = J. 
 | last2 = Simonovits | first2 = M. 
 | contribution = Szemerédi's regularity lemma and its applications in graph theory
 | mr = 1395865
 | pages = 295–352
 | publisher = János Bolyai Math. Soc., Budapest
 | series = Bolyai Soc. Math. Stud.
 | title = Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993)
 | volume = 2
 | year = 1996}}.
*{{citation
 | last1 = Komlós | first1 = J. 
 | last2 = Shokoufandeh | first2 = Ali
 | last3 = Simonovits | first3 = Miklós 
 | last4 = Szemerédi | first4 = Endre | author4-link = 塞迈雷迪·安德烈
 | contribution = The regularity lemma and its applications in graph theory
 | doi = 10.1007/3-540-45878-6_3
 | mr = 1966181
 | pages = 84–112
 | publisher = Springer, Berlin
 | series = Lecture Notes in Computer Science
 | title = Theoretical aspects of computer science (Tehran, 2000)
 | volume = 2292
 | year = 2002}}.

[[Category:圖論|S]]
[[Category:组合数学|S]]
[[Category:信息论|S]]
[[Category:引理|S]]