A Szemerédi-féle regularitási lemma egy gráfokra vonatkozó tétel, amely a kombinatorika számos tételének bizonyításában fontos és hatékony szerepet játszik, az extremális gráfelmélet központi eszköze. A tétel szerint minden, kellően nagy gráf felosztható olyan hasonló méretű részhalmazokra, ahol a részhalmazok közötti élek csaknem véletlenszerűek.Tehát felosztható olyan módon, hogy bármely két részhalmaz között futó élek szerkezete nagyon hasonló ahhoz, mintha a két részhalmaz között minden lehetséges élt egymástól függetlenül egy bizonyos valószínűséggel húznánk be.

Szemerédi Endre először a lemma egy gyengébb (csak páros gráfokra vonatkozó), a nevezetes Szemerédi-tétel bizonyításához szükséges változatát fogalmazta meg (Szemerédi 1975), majd még ugyanabban az évben egy másik munkájában igazolta a teljes lemmát. Később Rödl és társszerzői,P. Frankl, V. Rödl: Extremal problems on set systems, Random Structures & Algorithms, 20 (2002), 131–164.V. Rödl, J. Skokan: Regularity lemma for uniform hypergraphs, Random Structures & Algorithms, 25 (2004), 1–42.B. Nagle, V. Rödl, M. Schacht: The Counting Lemma for regular k-uniform hypergraphs, Random Structures & Algorithms, 28 (2006), 113–179 valamint GowersW. T. Gowers: Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, Combinatorics, Probability and Computing, 15 (2006), 143–184.W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, 166 (2007), 897–946. kiterjesztették a módszert hipergráfokra is.

Definíciók Egy gráf esetén, ha , jelölje e(A,B) az A és B közötti élek számát, .

Ha , akkor (A,B) pár -reguláris, ha minden , esetén, ha és , akkor teljesül.

A regularitási lemma állítása Ha adott az szám és természetes szám, akkor léteznek M és N természetes számok, hogy a következő állítás igaz: ha G gráf a V halmazon, ahol , akkor V particionálható a halmazokra, hogy , , , kivételével minden pár -reguláris.

Bizonyítása A lemma bizonyítása vázlatosan úgy történik, hogy V minden partíciójához, ami kielégíti a fenti 2., 3. tulajdonságot, hozzárendeljük az

mennyiséget. Erre mindig teljesül . Ezután belátjuk, hogy ha egy partícióban több, mint pár nem -reguláris, akkor van egy P-t finomító Q partíció legfeljebb részre, amire

teljesül. Ezután legfeljebb lépésben eljutunk egy, a lemma állítását kielégítő partícióhoz, ahol a részek száma legfeljebb , ahol az f függvényt az , rekurzióval definiáljuk.

Általánosításai

Jegyzetek

További információk Tóth Ágnes: A Szemerédi-lemma és alkalmazásai M. Simonovits: Megjegyzések a Regularity Lemmáról – miről beszélünk? W. T. Gowers: The Work of Endre Szemerédi

Kategória:Gráfelmélet Kategória:Kombinatorika Kategória:Lemmák