极值图论中,埃尔德什-斯通定理(英语:Erdős–Stone theorem)是禁止某子图
出现后,图边数的渐近上界,推广了图兰定理(即仅允许
为完全图的情况)。定理由埃尔德什·帕尔与阿瑟·斯通于1946年证明[1],因而得名。博洛巴什·贝洛称其为“极值图论的基本定理”。[2]
图兰图的极值函数[编辑]
先定义极值函数(英语:extremal function)
如下:
是众多
个顶点的图之中,不包含子图(同构于)
的图的边数最大值。图兰定理断言,当
取为完全图
时,有
,即
个顶点的
部图兰图的边数,且仅得该图兰图取到最大值。埃尔德什-斯通定理推广到禁止
子图的情况,即禁止各分部恰有
个顶点的完全
部图(亦可记为图兰图
):
![{\displaystyle {\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8ae86a1b8d036247947726ce44f3d5fbbdb5c56)
任意非二部图的极值函数[编辑]
若
为任意图,色数为
,则对于足够大的
,
必为
的子图(比如取
大于
的某个
染色中,用得最多的颜色所用的次数),但
并非图兰图
的子图,因为该图兰图的任意子图皆可
染色。
由此可见,
的极值函数至少为
的边数,但至多为
的极值函数。所以,仍有
![{\displaystyle {\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4084a1e177d691e64a5392332b8152bf66a3f26d)
然而,对于二部图
,定理给出的上界并非最优,因为已知当
为二部图时,
,不过对于一般二部图的极值函数,仍然所知甚少,见扎兰凯维奇问题。
定量结果[编辑]
定理亦有若干个定量版本已获证,较确切刻划
与馀项
的关系。先对
,定义[3]
为最大的
,使得子图
能于任意具
个顶点及
![{\displaystyle \left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c24989cca9d7537e17b887f36d1e04a1a531f33)
条边的图中找到。
埃尔德什、斯通证明对充份大的
,有
![{\displaystyle s_{r,\varepsilon }(n)\geq \left(\log ^{r-1}n\right)^{1/2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a79b71bcfb0b4a4afa2084fcc4b859b039a714f)
其中
是对数函数的
次叠代。
的正确增长阶数,由博洛巴什与埃尔德什找出:[4]固定
,则存在常数
与
使得
![{\displaystyle c_{1}(r,\varepsilon )\log n<s_{r,\varepsilon }(n)<c_{2}(r,\varepsilon ).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58b9faf9e1ad1903532e4dbf93ad40182bc27eec)
赫瓦塔尔与塞迈雷迪[5]随后确定
如何随
和
变化(但可以差常数倍):对充份大的
,有
![{\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a63b5dd9bfd22b21c1065abed133e569b7fd497)
参考文献[编辑]
- ^ 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
(英语).
- ^ Bollobás, Béla. Modern Graph Theory [近世图论]. New York: Springer-Verlag. 1998: 120. ISBN 0-387-98491-7 (英语).
- ^ 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 (英语).
- ^ 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 (英语).
- ^ 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 (英语).