艾狄胥-斯通定理

極值圖論中，艾狄胥－斯通定理（英語：Erdős–Stone theorem）是禁止某子圖$H$出現後，圖邊數的漸近上界，推廣了圖蘭定理（即僅允許$H$為完全圖的情況）。定理由艾狄胥·帕爾與阿瑟·斯通於1946年證明，因而得名。博洛巴什·貝洛稱其為「極值圖論的基本定理」。

圖蘭圖的極值函數

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

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

任意非二部圖的極值函數

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

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

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

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

定量結果

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

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

條邊的圖中找到。

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

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

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

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

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

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