艾狄胥-斯通定理

極值圖論（英语：extremal graph theory）中，艾狄胥－斯通定理（英語：Erdős–Stone theorem）是禁止某子圖${\displaystyle H}$出現後，圖邊數的漸近上界，推廣了图兰定理（即僅允許${\displaystyle H}$為完全圖的情況）。定理由埃尔德什·帕尔與亞瑟·斯通（英语：Arthur Stone (mathematician)）於1946年證明^[1]，因而得名。博洛巴什·貝洛（英语：Béla Bollobás）稱其為「極值圖論的基本定理（英语：fundamental theorem）」。^[2]

圖蘭圖的極值函數

先定義極值函數（英語：extremal function）${\displaystyle \mathrm {ex} }$ 如下：${\displaystyle \mathrm {ex} (n;H)}$ 是眾多${\displaystyle n}$ 個頂點的圖之中，不包含子圖（同構於）${\displaystyle H}$ 的圖的邊數最大值。圖蘭定理斷言，當${\displaystyle H}$ 取為完全圖${\displaystyle K_{r}}$ 時，有${\displaystyle \mathrm {ex} (n;K_{r})=t_{r-1}(n)}$ ，即${\displaystyle n}$ 個頂點的${\displaystyle r-1}$ 部圖蘭圖（英语：Turán graph）的邊數，且僅得該圖蘭圖取到最大值。艾狄胥－斯通定理推廣到禁止${\displaystyle K_{r}(t)}$ 子圖的情況，即禁止各分部恰有${\displaystyle t}$ 個頂點的完全${\displaystyle r}$ 部圖（亦可記為圖蘭圖（英语：Turán graph）${\displaystyle T(rt,r)}$ ）：

${\displaystyle {\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$ 

任意非二部圖的極值函數

若${\displaystyle H}$ 為任意圖，色數為${\displaystyle r>2}$ ，則對於足夠大的${\displaystyle t}$ ，${\displaystyle H}$ 必為${\displaystyle K_{r}(t)}$ 的子圖（比如取${\displaystyle t}$ 大於${\displaystyle H}$ 的某個${\displaystyle r}$ 染色中，用得最多的顏色所用的次數），但${\displaystyle H}$ 並非圖蘭圖${\displaystyle T(n,r-1)}$ 的子圖，因為該圖蘭圖的任意子圖皆可${\displaystyle r-1}$ 染色。

由此可見，${\displaystyle H}$ 的極值函數至少為${\displaystyle T(n,r-1)}$ 的邊數，但至多為${\displaystyle K_{r}(t)}$ 的極值函數。所以，仍有

${\displaystyle {\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}$ 

然而，對於二部圖${\displaystyle H}$ ，定理給出的上界並非最優，因為已知當${\displaystyle H}$ 為二部圖時，${\displaystyle \mathrm {ex} (n;H)=o(n^{2})}$ ，不過對於一般二部圖的極值函數，仍然所知甚少，見扎蘭凱維奇問題（英语：Zarankiewicz problem）。

定量結果

定理亦有若干個定量版本已獲證，較確切刻劃${\displaystyle n,r,t}$ 與餘項${\displaystyle o(1)}$ 的關係。先對${\displaystyle 0<\varepsilon <1/(2(r-1))}$ ，定義^[3]${\displaystyle s_{r,\varepsilon }(n)}$ 為最大的${\displaystyle t}$ ，使得子圖${\displaystyle K_{r}(t)}$ 能於任意具${\displaystyle n}$ 個頂點及

${\displaystyle \left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}}$ 

條邊的圖中找到。

艾狄胥、斯通證明對充份大的${\displaystyle n}$ ，有

${\displaystyle s_{r,\varepsilon }(n)\geq \left(\log ^{r-1}n\right)^{1/2},}$ 

其中${\displaystyle \log ^{r-1}}$ 是對數函數的${\displaystyle r-1}$ 次疊代。${\displaystyle s_{r,\varepsilon }(n)}$ 的正確增長階數，由博洛巴什與艾狄胥找出：^[4]固定${\displaystyle r,\varepsilon }$ ，則存在常數${\displaystyle c_{1}(r,\varepsilon )}$ 與${\displaystyle c_{2}(r,\varepsilon )}$ 使得

${\displaystyle c_{1}(r,\varepsilon )\log n<s_{r,\varepsilon }(n)<c_{2}(r,\varepsilon ).}$ 

赫瓦塔爾與塞邁雷迪^[5]隨後確定${\displaystyle s_{r,\varepsilon }(n)}$ 如何隨${\displaystyle r}$ 和${\displaystyle \varepsilon }$ 變化（但可以差常數倍）：對充份大的${\displaystyle n}$ ，有

${\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n.}$ 

參考文獻

1. Erdős, P.; Stone, A. H. On the structure of linear graphs [論線段圖的結構]. Bulletin of the American Mathematical Society. 1946, 52 (12): 1087–1091. doi:10.1090/S0002-9904-1946-08715-7   （英语）. 
2. Bollobás, Béla. Modern Graph Theory [近世圖論]. New York: Springer-Verlag. 1998: 120. ISBN 0-387-98491-7 （英语）. 
3. Bollobás, Béla. Extremal graph theory [極值圖論]. R. L. Graham; M. Grötschel; L. Lovász (编). Handbook of combinatorics [組合手冊]. Elsevier. 1995: 1244. ISBN 0-444-88002-X （英语）. 
4. Bollobás, B.; Erdős, P. On the structure of edge graphs [論邊圖的結構]. Bulletin of the London Mathematical Society. 1973, 5 (3): 317–321. doi:10.1112/blms/5.3.317 （英语）. 
5. Chvátal, V.; Szemerédi, E. On the Erdős-Stone theorem [論艾狄胥－斯通定理]. Journal of the London Mathematical Society. 1981, 23 (2): 207–214. doi:10.1112/jlms/s2-23.2.207 （英语）.