埃尔德什-斯通定理

极值图论（英语：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 （英语）.