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; Kr) = tr − 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 Kr(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):
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 Kr(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 Kr(t)-hez tartozó extremális függvényérték; azaz,
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(n2), é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: sr,ε(n) (ahol 0 < ε < 1/(2(r − 1))) legyen a legnagyobb olyan t, amire minden n csúcsból és
élből álló gráf tartalmazza Kr(t)-t.
Erdős és Stone bebizonyították, hogy elegendően nagy n-re . Először az sr,ε(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 c1(r, ε) és c2(r, ε) konstansok, melyekre c1(r, ε) log n < sr,ε(n) < c2(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: elegendően nagy n-re.
További információk Extremal graphs and the Erdős-Stone-Simonovits theorems
Fordítás
Jegyzetek
Kategória:Extremális gráfelmélet Kategória:Gráfelméleti tételek Kategória:Erdős Pál