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):

${\mbox{ex}}(n;K_{r}(t))=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 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,

${\mbox{ex}}(n;H)=\left({\frac {r-2}{r-1}}+o(1)\right){n \choose 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

$\left({\frac {r-2}{2(r-1)}}+\varepsilon \right)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,\varepsilon }(n)\geq \left(\underbrace {\log \cdots \log } _{r-1}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/\varepsilon )}}\log n<s_{r,\varepsilon }(n)<{\frac {5}{\log(1/\varepsilon )}}\log n$ elegendően nagy n-re.

További információk

• Extremal graphs and the Erdős-Stone-Simonovits theorems

Fordítás

• Ez a szócikk részben vagy egészben az Erdős–Stone theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.