中，埃尔德什－斯通定理（）是禁止某子圖H出現後，圖邊數的漸近上界，推廣了图兰定理（即僅允許H為完全圖的情況）。定理由埃尔德什·帕尔與於1946年證明，因而得名。稱其為「極值圖論的基本定理」。
圖蘭圖的極值函數
先定義極值函數（）\mathrm{ex}如下：\mathrm{ex}(n; H)是眾多n個頂點的圖之中，不包含子圖（同構於）H的圖的邊數最大值。圖蘭定理斷言，當H取為完全圖K_r時，有\mathrm{ex}(n; K_r) = t_{r-1}(n)，即n個頂點的r-1部圖蘭圖的邊數，且僅得該圖蘭圖取到最大值。埃尔德什－斯通定理推廣到禁止K_r(t)子圖的情況，即禁止各分部恰有t個頂點的完全r部圖（亦可記為圖蘭圖T(rt, r)）：
:\mbox{ex}(n; K_r(t)) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.
任意非二部圖的極值函數
若H為任意圖，色數為r > 2，則對於足夠大的t，H必為K_r(t)的子圖（比如取t大於H的某個r染色中，用得最多的顏色所用的次數），但H並非圖蘭圖T(n, r-1)的子圖，因為該圖蘭圖的任意子圖皆可r-1染色。
由此可見，H的極值函數至少為T(n, r-1)的邊數，但至多為K_r(t)的極值函數。所以，仍有
:\mbox{ex}(n; H) = \left( \frac{r-2}{r-1} + o(1) \right){n\choose2}.
然而，對於二部圖H，定理給出的上界並非最優，因為已知當H為二部圖時，\mathrm{ex}(n;H) = o(n^2)，不過對於一般二部圖的極值函數，仍然所知甚少，見。
定量結果
定理亦有若干個定量版本已獲證，較確切刻劃n, r, t與餘項o(1)的關係。先對0 ，定義s_{r, \varepsilon}(n)為最大的t，使得子圖K_r(t)能於任意具n個頂點及
:\left( \frac{r-2}{2(r-1)} + \varepsilon \right)n^2
條邊的圖中找到。
埃尔德什、斯通證明對充份大的n，有
:s_{r,\varepsilon}(n) \geq \left(\log^{r-1} n\right)^{1/2},
其中\log^{r-1}是對數函數的r-1次疊代。s_{r, \varepsilon}(n)的正確增長階數，由博洛巴什與埃尔德什找出：固定r, \varepsilon，則存在常數c_1(r, \varepsilon)與c_2(r, \varepsilon)使得
:c_1(r, \varepsilon) \log n
赫瓦塔爾與塞邁雷迪隨後確定s_{r, \varepsilon}(n)如何隨r和\varepsilon變化（但可以差常數倍）：對充份大的n，有
:\frac{1}{500\log(1/\varepsilon)}\log n
參考文獻
评论 (0)