跳至內容

艾狄胥-斯通定理

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

極值圖論英語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 (英語).