艾狄胥-斯通定理

極值圖論中,禁止子圖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 (英语).