埃尔德什-斯通定理

极值图论中，埃尔德什－斯通定理（英语：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.$