極值圖論中,埃尔德什-斯通定理(英語:Erdős–Stone theorem)是禁止某子圖
出現後,圖邊數的漸近上界,推廣了图兰定理(即僅允許
為完全圖的情況)。定理由埃尔德什·帕尔與阿瑟·斯通於1946年證明[1],因而得名。博洛巴什·貝洛稱其為「極值圖論的基本定理」。[2]
先定義極值函數(英語:extremal function)
如下:
是眾多
個頂點的圖之中,不包含子圖(同構於)
的圖的邊數最大值。圖蘭定理斷言,當
取為完全圖
時,有
,即
個頂點的
部圖蘭圖的邊數,且僅得該圖蘭圖取到最大值。埃尔德什-斯通定理推廣到禁止
子圖的情況,即禁止各分部恰有
個頂點的完全
部圖(亦可記為圖蘭圖
):
![{\displaystyle {\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/a8ae86a1b8d036247947726ce44f3d5fbbdb5c56)
若
為任意圖,色數為
,則對於足夠大的
,
必為
的子圖(比如取
大於
的某個
染色中,用得最多的顏色所用的次數),但
並非圖蘭圖
的子圖,因為該圖蘭圖的任意子圖皆可
染色。
由此可見,
的極值函數至少為
的邊數,但至多為
的極值函數。所以,仍有
![{\displaystyle {\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 2}.}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/4084a1e177d691e64a5392332b8152bf66a3f26d)
然而,對於二部圖
,定理給出的上界並非最優,因為已知當
為二部圖時,
,不過對於一般二部圖的極值函數,仍然所知甚少,見扎蘭凱維奇問題。
定理亦有若干個定量版本已獲證,較確切刻劃
與餘項
的關係。先對
,定義[3]
為最大的
,使得子圖
能於任意具
個頂點及
![{\displaystyle \left({\frac {r-2}{2(r-1)}}+\varepsilon \right)n^{2}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/9c24989cca9d7537e17b887f36d1e04a1a531f33)
條邊的圖中找到。
埃尔德什、斯通證明對充份大的
,有
![{\displaystyle s_{r,\varepsilon }(n)\geq \left(\log ^{r-1}n\right)^{1/2},}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/6a79b71bcfb0b4a4afa2084fcc4b859b039a714f)
其中
是對數函數的
次疊代。
的正確增長階數,由博洛巴什與埃尔德什找出:[4]固定
,則存在常數
與
使得
![{\displaystyle c_{1}(r,\varepsilon )\log n<s_{r,\varepsilon }(n)<c_{2}(r,\varepsilon ).}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/58b9faf9e1ad1903532e4dbf93ad40182bc27eec)
赫瓦塔爾與塞邁雷迪[5]隨後確定
如何隨
和
變化(但可以差常數倍):對充份大的
,有
![{\displaystyle {\frac {1}{500\log(1/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n.}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/3a63b5dd9bfd22b21c1065abed133e569b7fd497)
- ^ 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 (英语).