Szemerédi-féle regularitási lemma

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.^[1]

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^[2]), majd még ugyanabban az évben egy másik munkájában^[3] igazolta a teljes lemmát. Később Rödl és társszerzői,^[4][5][6] valamint Gowers^[7][8] kiterjesztették a módszert hipergráfokra is.

Definíciók

Egy ${\displaystyle X=(V,E)}$ gráf esetén, ha ${\displaystyle A,B\subseteq V}$, jelölje e(A,B) az A és B közötti élek számát, ${\displaystyle d(A,B)=e(A,B)/|A||B|}$.

Ha ${\displaystyle \varepsilon >0}$, akkor (A,B) pár ${\displaystyle \varepsilon }$-reguláris, ha minden ${\displaystyle A'\subseteq A}$, ${\displaystyle B'\subseteq B}$ esetén, ha ${\displaystyle |A'|>\varepsilon |A|}$ és ${\displaystyle |B'|>\varepsilon |B|}$, akkor ${\displaystyle |d(A',B')-d(A,B)|<\varepsilon }$ teljesül.

A regularitási lemma állítása

Ha adott az ${\displaystyle \varepsilon >0}$ szám és ${\displaystyle m}$ 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 ${\displaystyle n=|V|\geq N}$, akkor V particionálható a ${\displaystyle V_{0},V_{1},\dots ,V_{k}}$ halmazokra, hogy

1. ${\displaystyle m\leq k\leq M}$,
2. ${\displaystyle |V_{0}|<\varepsilon n}$,
3. ${\displaystyle |V_{1}|=|V_{2}|=\cdots =|V_{k}|}$,
4. ${\displaystyle \varepsilon k^{2}}$ kivételével minden ${\displaystyle (V_{i},V_{j})}$ pár ${\displaystyle \varepsilon }$-reguláris.

Bizonyítása

A lemma bizonyítása vázlatosan úgy történik, hogy V minden ${\displaystyle P=(V_{0},\dots ,V_{k})}$ partíciójához, ami kielégíti a fenti 2., 3. tulajdonságot, hozzárendeljük az

${\displaystyle {\text{ind}}(P)={\frac {1}{k^{2}}}\sum _{i=1}^{k}\sum _{j=i+1}^{k}d^{2}(V_{i},V_{j})}$

mennyiséget. Erre mindig teljesül ${\displaystyle {\text{ind}}(P)\leq {\frac {1}{2}}}$. Ezután belátjuk, hogy ha egy ${\displaystyle P=(V_{0},V_{1},\dots ,V_{k})}$ partícióban több, mint ${\displaystyle \varepsilon k^{2}}$ pár nem ${\displaystyle \varepsilon }$-reguláris, akkor van egy P-t finomító Q partíció legfeljebb ${\displaystyle 1+k4^{k}}$ részre, amire

${\displaystyle {\text{ind}}(Q)\geq {\text{ind}}(P)+{\frac {\varepsilon ^{5}}{20}}}$

teljesül. Ezután legfeljebb ${\displaystyle 10/\varepsilon ^{5}}$ lépésben eljutunk egy, a lemma állítását kielégítő partícióhoz, ahol a részek száma legfeljebb ${\displaystyle f(10/\varepsilon ^{5})}$, ahol az f függvényt az ${\displaystyle f(0)=m}$, ${\displaystyle f(t+1)=1+f(t)4^{f(t)}}$ 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