艾狄胥-斯通定理

Template:Eastern name order Template:NoteTA Template:Link-en中，埃尔德什－斯通定理（Template:Lang-en）是禁止某子圖$H$出現後，圖邊數的漸近上界，推廣了图兰定理（即僅允許$H$為完全圖的情況）。定理由埃尔德什·帕尔與Template:Link-en於1946年證明，因而得名。Template:Le稱其為「極值圖論的Template:Le」。

圖蘭圖的極值函數

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

$\text{ex}(n;K_r(t))=(\frac{r-2}{r-1}+o(1))(\genfrac{}{}{0ex}{}{n}{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)$的極值函數。所以，仍有

$\text{ex}(n;H)=(\frac{r-2}{r-1}+o(1))(\genfrac{}{}{0ex}{}{n}{2}).$

然而，對於二部圖$H$，定理給出的上界並非最優，因為已知當$H$為二部圖時，$\mathrm{e}\mathrm{x}(n;H)=o(n^2)$，不過對於一般二部圖的極值函數，仍然所知甚少，見Template:Link-en。

定量結果

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

$(\frac{r-2}{2(r-1)}+\epsilon )n^2$

條邊的圖中找到。

埃尔德什、斯通證明對充份大的$n$，有

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

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

$c_1(r,\epsilon )\log n<s_{r,\epsilon }(n)<c_2(r,\epsilon ).$

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

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