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é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:[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ók
- Extremal graphs and the Erdős-Stone-Simonovits theorems[halott link]
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.
Jegyzetek
- ↑ 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.
- ↑ Bollobás, Béla. Modern Graph Theory. New York: Springer-Verlag, 120. o. (1998). ISBN 0-387-98491-7
- ↑ 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
- ↑ 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.
- ↑ 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.