跳转到内容

埃尔德什-斯通定理

本页使用了标题或全文手工转换
维基百科,自由的百科全书

极值图论英语extremal graph theory中,埃尔德什-斯通定理(英语:Erdős–Stone theorem)是禁止某子图出现后,图边数的渐近上界,推广了图兰定理(即仅允许完全图的情况)。定理由埃尔德什·帕尔阿瑟·斯通英语Arthur Stone (mathematician)于1946年证明[1],因而得名。博洛巴什·贝洛英语Béla Bollobás称其为“极值图论的基本定理英语fundamental theorem”。[2]

图兰图的极值函数

[编辑]

先定义极值函数(英语:extremal function如下:是众多个顶点的图之中,不包含子图(同构于)的图的边数最大值。图兰定理断言,当取为完全图时,有,即个顶点的图兰图英语Turán graph的边数,且仅得该图兰图取到最大值。埃尔德什-斯通定理推广到禁止子图的情况,即禁止各分部恰有个顶点的完全部图(亦可记为图兰图英语Turán graph):

任意非二部图的极值函数

[编辑]

为任意图,色数,则对于足够大的必为的子图(比如取大于的某个染色中,用得最多的颜色所用的次数),但并非图兰图的子图,因为该图兰图的任意子图皆可染色。

由此可见,的极值函数至少为的边数,但至多为的极值函数。所以,仍有

然而,对于二部图,定理给出的上界并非最优,因为已知当为二部图时,,不过对于一般二部图的极值函数,仍然所知甚少,见扎兰凯维奇问题英语Zarankiewicz problem

定量结果

[编辑]

定理亦有若干个定量版本已获证,较确切刻划余项的关系。先对,定义[3]为最大的,使得子图能于任意具个顶点及

条边的图中找到。

埃尔德什、斯通证明对充份大的,有

其中是对数函数的次迭代。的正确增长阶数,由博洛巴什与埃尔德什找出:[4]固定,则存在常数使得

赫瓦塔尔与塞迈雷迪[5]随后确定如何随变化(但可以差常数倍):对充份大的,有

参考文献

[编辑]
  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 (英语).