查看“︁艾狄胥-斯通定理”︁的源代码

{{Eastern name order|匈牙利文|匈牙利人名}}
{{noteTA
|1=zh-hans:埃尔德什; zh-hant:艾狄胥;
}}
{{link-en|極值圖論|extremal graph theory}}中，'''埃尔德什－斯通定理'''（{{lang-en|Erdős–Stone theorem}}）是禁止某子圖<math>H</math>出現後，圖邊數的[[漸近分析|漸近]]上界，推廣了[[图兰定理]]（即僅允許<math>H</math>為[[完全圖]]的情況）。定理由[[埃尔德什·帕尔]]與{{link-en|阿瑟·斯通 (數學家)|Arthur Stone (mathematician)|阿瑟·斯通}}於1946年證明<ref>{{cite journal |last=Erdős |first=P. |author-link=Paul Erdős |author2=Stone, A. H. |year=1946 |title=On the structure of linear graphs|trans-title = 論線段圖的結構 |journal=Bulletin of the American Mathematical Society |volume=52  |pages=1087–1091 |doi=10.1090/S0002-9904-1946-08715-7 |issue=12|doi-access=free |language = en}}</ref>，因而得名。{{le|博洛巴什·貝洛|Béla Bollobás}}<!--按[[WP:外語譯音表/匈牙利語]]暫譯-->稱其為「極值圖論的{{le|基本定理|fundamental theorem}}」。<ref>{{cite book |last=Bollobás |first=Béla |title=Modern Graph Theory |trans-title = 近世圖論|url=https://archive.org/details/moderngraphtheor00bbol_656 |year=1998 |publisher=[[施普林格科学+商业媒体|Springer-Verlag]] |location=New York |isbn=0-387-98491-7 |pages=[https://archive.org/details/moderngraphtheor00bbol_656/page/n135 120] |language = en}}</ref>

==圖蘭圖的極值函數==
先定義'''極值函數'''（{{lang-en|extremal function}}）<math>\mathrm{ex}</math>如下：<math>\mathrm{ex}(n; H)</math>是眾多<math>n</math>個頂點的圖之中，不包含子圖（同構於）<math>H</math>的圖的邊數最大值。[[圖蘭定理]]斷言，當<math>H</math>取為[[完全圖]]<math>K_r</math>時，有<math>\mathrm{ex}(n; K_r) = t_{r-1}(n)</math>，即<math>n</math>個頂點的<math>r-1</math>部{{link-en|圖蘭圖|Turán graph}}的邊數，且僅得該圖蘭圖取到最大值。埃尔德什－斯通定理推廣到禁止<math>K_r(t)</math>子圖的情況，即禁止各分部恰有<math>t</math>個頂點的[[多分圖|完全<math>r</math>部圖]]（亦可記為{{link-en|圖蘭圖|Turán graph}}<math>T(rt, r)</math>）：

:<math>\mbox{ex}(n; K_r(t)) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.</math>

==任意非二部圖的極值函數==
若<math>H</math>為任意圖，[[图着色问题|色數]]為<math>r > 2</math>，則對於足夠大的<math>t</math>，<math>H</math>必為<math>K_r(t)</math>的子圖（比如取<math>t</math>大於<math>H</math>的某個<math>r</math>染色中，用得最多的顏色所用的次數），但<math>H</math>並非圖蘭圖<math>T(n, r-1)</math>的子圖，因為該圖蘭圖的任意子圖皆可<math>r-1</math>染色。 

由此可見，<math>H</math>的極值函數至少為<math>T(n, r-1)</math>的邊數，但至多為<math>K_r(t)</math>的極值函數。所以，仍有
:<math>\mbox{ex}(n; H) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.</math>

然而，對於[[二分图|二部圖]]<math>H</math>，定理給出的上界並非最優，因為已知當<math>H</math>為二部圖時，<math>\mathrm{ex}(n;H) = o(n^2)</math>，不過對於一般二部圖的極值函數，仍然所知甚少，見{{link-en|扎蘭凱維奇問題|Zarankiewicz problem}}<!--照用[[交叉數]]中的譯法-->。

==定量結果==

定理亦有若干個定量版本已獲證，較確切刻劃<math>n, r, t</math>與[[小o符號|餘項<math>o(1)</math>]]的關係。先對<math>0 < \varepsilon < 1/(2(r - 1))</math>，定義<ref>{{cite book |last=Bollobás |first=Béla |editor= R. L. Graham |editor-link= 葛立恆 |editor2=M. Grötschel  |editor3=L. Lovász |editor3-link=洛瓦茲·拉茲洛 |title=Handbook of combinatorics |trans-title = 組合手冊 |year=1995 |publisher=[[愛思唯爾|Elsevier]] |isbn=0-444-88002-X |pages=1244 |chapter=Extremal graph theory |trans-chapter = 極值圖論|language = en}}</ref><math>s_{r, \varepsilon}(n)</math>為最大的<math>t</math>，使得子圖<math>K_r(t)</math>能於任意具<math>n</math>個頂點及

:<math>\left( \frac{r-2}{2(r-1)} + \varepsilon \right)n^2</math>

條邊的圖中找到。

埃尔德什、斯通證明對充份大的<math>n</math>，有
:<math>s_{r,\varepsilon}(n) \geq \left(\log^{r-1} n\right)^{1/2},</math>
其中<math>\log^{r-1}</math>是對數函數的<math>r-1</math>次疊代。<math>s_{r, \varepsilon}(n)</math>的正確增長階數，由博洛巴什與埃尔德什找出：<ref>{{cite journal |last=Bollobás |first=B. |author2=Erdős, P. |authorlink2=Paul Erdős  |year=1973 |title=On the structure of edge graphs|trans-title = 論邊圖的結構 |journal=Bulletin of the London Mathematical Society |volume=5 |pages=317–321 |doi=10.1112/blms/5.3.317 |issue=3 |language = en}}</ref>固定<math>r, \varepsilon</math>，則存在常數<math>c_1(r, \varepsilon)</math>與<math>c_2(r, \varepsilon)</math>使得

:<math>c_1(r, \varepsilon) \log n < s_{r, \varepsilon}(n) < c_2(r, \varepsilon).</math>
赫瓦塔爾與[[塞邁雷迪·安德烈|塞邁雷迪]]<ref>{{cite journal |last=Chvátal |first=V.  |author2=Szemerédi, E. |authorlink2=塞邁雷迪·安德烈  |year=1981 |title=On the Erdős-Stone theorem|trans-title = 論埃尔德什－斯通定理 |journal=Journal of the London Mathematical Society |volume=23 |issue=2 |pages=207–214 |doi=10.1112/jlms/s2-23.2.207 |language = en}}</ref>隨後確定<math>s_{r, \varepsilon}(n)</math>如何隨<math>r</math>和<math>\varepsilon</math>變化（但可以差常數倍）：對充份大的<math>n</math>，有
:<math>\frac{1}{500\log(1/\varepsilon)}\log n < s_{r,\varepsilon}(n) < \frac{5}{\log(1/\varepsilon)}\log n.</math>

==參考文獻==
{{Reflist}}

{{DEFAULTSORT:Erdos-Stone theorem}}

{{圖論}}
[[Category:图论]]
[[Category:数学定理]]