埃尔德什-斯通定理

極值圖論中,禁止子圖H之後,邊數的上界與H的色數有關

极值图论英语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 (英语).