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,.[1] Később „az extremális gráfelmélet alaptételének” is nevezték.[2]

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

Az ex(nH) 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(nKr) = 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ényeiSzerkesztés

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(nH) = 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ényekSzerkesztés

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:[3] 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:[4] 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[5] 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ókSzerkesztés

FordításSzerkeszté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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Erdős, P. (1946). „On the structure of linear graphs”. Bulletin of the American Mathematical Society 52 (12), 1087–1091. o. DOI:10.1090/S0002-9904-1946-08715-7.  
  2. Bollobás, Béla. Modern Graph Theory. New York: Springer-Verlag, 120. o. (1998). ISBN 0-387-98491-7 
  3. Bollobás, Béla.szerk.: R. L. Graham, M. Grötschel and L. Lovász (eds.): Extremal graph theory, Handbook of combinatorics. Elsevier, 1244. o. (1995). ISBN 0-444-88002-X 
  4. Bollobás, B. (1973). „On the structure of edge graphs”. Bulletin of the London Mathematical Society 5 (3), 317–321. o. DOI:10.1112/blms/5.3.317.  
  5. Chvátal, V. (1981). „On the Erdős-Stone theorem”. Journal of the London Mathematical Society 23 (2), 207–214. o. DOI:10.1112/jlms/s2-23.2.207.