Erdős–Stone-tétel

A matematika, a gráfelmélet, azon belül az extremális gráfelmélet területén az Erdős–Stone-tétel a Turán-tételt általánosító aszimptotikus eredmény; míg a Turán-tétel a teljes gráfmentességgel foglalkozik, az Erdős–Stone-tétel a H-mentes (ahol H egy nem teljes gráf) gráfok éleinek számára állapít meg korlátot. Nevét Erdős Pál és Arthur Stone matematikusokról kapta, akik 1946-ban bizonyították,. Később „az extremális gráfelmélet alaptételének” is nevezték.

Turán-gráfok extremális függvényei

Az ex(n; H) extremális függvényt úgy határozzuk meg, mint az olyan gráfok maximális éleinek számát, mely csúcsainak száma n és nem tartalmaz H-val izomorf részgráfot. A Turán-tétel szerint ex(n; K_r) = t_r − 1(n), ami a Turán-gráf rendje, és a Turán-gráf az egyetlen extremális gráf. Az Erdős–Stone-tétel kiterjeszti az eredményt a K_r(t)-t nem tartalmazó gráfokra; méghozzá a teljes r-részes gráfokra, melyeknél minden csoportban t csúcs található (vagy ezzel ekvivalens módon, a T(rt,r) Turán-gráfokra):

$\text{ex}(n;K_r(t))=(\frac{r-2}{r-1}+o(1))(\genfrac{}{}{0ex}{}{n}{2}).$

Tetszőleges nem páros gráfok extremális függvényei

Ha H tetszőleges gráf, melynek kromatikus száma r > 2, akkor H minden olyan esetben benne van K_r(t)-ben, amikor t legalább akkora, mint a H r-színezésének legnagyobb színosztálya, de nincs benne a T(n,r − 1) Turán-gráfban (hiszen ennek a Turán-gráfnak minden részgráfja r − 1 színnel színezhető). Következésképpen a H-hoz tartozó extremális függvényérték legalább akkora, mint T(n,r − 1) éleinek száma, és legfeljebb akkora, mint a K_r(t)-hez tartozó extremális függvényérték; azaz,

$\text{ex}(n;H)=(\frac{r-2}{r-1}+o(1))(\genfrac{}{}{0ex}{}{n}{2}).$

Ha H páros gráf, a tétel nem ad éles korlátot az extremális függvényre. Ismert, hogy ha H páros, akkor ex(n; H) = o(n²), és az általános páros gráfokról ennél többet nem nagyon tudunk elmondani. A páros gráfok extremális függvényeiről lásd még: Zarankiewicz-probléma.

Kvantitatív eredmények

A tétel számos verzióját igazolták, melyek pontosabban írják le n, r, t és az o(1) tag kapcsolatát. Vezessük be a következő jelölést: s_r,ε(n) (ahol 0 < ε < 1/(2(r − 1))) legyen a legnagyobb olyan t, amire minden n csúcsból és

$(\frac{r-2}{2(r-1)}+\epsilon )n^2$

élből álló gráf tartalmazza K_r(t)-t.

Erdős és Stone bebizonyították, hogy elegendően nagy n-re

$s_{r,\epsilon }(n)\ge {\left(\underset{r-1}{\underbrace{\log \cdots \log }}n\right)}^{1/2}$.

Először az s_r,ε(n) helyes sorrendjét kellett megállapítani az n tagok szerint, ezt Bollobás és Erdős végezte el: bármely adott r és ε-ra léteznek olyan c₁(r, ε) és c₂(r, ε) konstansok, melyekre c₁(r, ε) log n < s_r,ε(n) < c₂(r, ε) log n. Chvátal és Szemerédi ezután meghatározták az r-től és ε-tól való függést, konstans erejéig:

$\frac{1}{500\log (1/\epsilon )}\log n<s_{r,\epsilon }(n)<\frac{5}{\log (1/\epsilon )}\log n$ elegendően nagy n-re.

További információk

• Extremal graphs and the Erdős-Stone-Simonovits theoremsSablon:Halott link

Fordítás

• Sablon:Fordítás