埃尔德什-斯通定理
極值圖論中,禁止子圖H之後,邊數的上界與H的色數有關
极值图论中,埃尔德什-斯通定理(英语:Erdős–Stone theorem)是禁止某子图出现后,图边数的渐近上界,推广了图兰定理(即仅允许为完全图的情况)。定理由埃尔德什·帕尔与阿瑟·斯通于1946年证明[1],因而得名。博洛巴什·贝洛称其为“极值图论的基本定理”。[2]
图兰图的极值函数
编辑先定义极值函数(英语:extremal function) 如下: 是众多 个顶点的图之中,不包含子图(同构于) 的图的边数最大值。图兰定理断言,当 取为完全图 时,有 ,即 个顶点的 部图兰图的边数,且仅得该图兰图取到最大值。埃尔德什-斯通定理推广到禁止 子图的情况,即禁止各分部恰有 个顶点的完全 部图(亦可记为图兰图 ):
任意非二部图的极值函数
编辑若 为任意图,色数为 ,则对于足够大的 , 必为 的子图(比如取 大于 的某个 染色中,用得最多的颜色所用的次数),但 并非图兰图 的子图,因为该图兰图的任意子图皆可 染色。
由此可见, 的极值函数至少为 的边数,但至多为 的极值函数。所以,仍有
然而,对于二部图 ,定理给出的上界并非最优,因为已知当 为二部图时, ,不过对于一般二部图的极值函数,仍然所知甚少,见扎兰凯维奇问题。
定量结果
编辑定理亦有若干个定量版本已获证,较确切刻划 与余项 的关系。先对 ,定义[3] 为最大的 ,使得子图 能于任意具 个顶点及
条边的图中找到。
埃尔德什、斯通证明对充份大的 ,有
其中 是对数函数的 次迭代。 的正确增长阶数,由博洛巴什与埃尔德什找出:[4]固定 ,则存在常数 与 使得
赫瓦塔尔与塞迈雷迪[5]随后确定 如何随 和 变化(但可以差常数倍):对充份大的 ,有
参考文献
编辑- ^ 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 (英语).