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.

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, valamint Gowers kiterjesztették a módszert hipergráfokra is.

Definíciók

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

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

A regularitási lemma állítása

Ha adott az $\epsilon >0$ szám és $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 $n=|V|\ge N$, akkor V particionálható a $V_0,V_1,\dots ,V_k$ halmazokra, hogy

1. $m\le k\le M$,
2. $|V_0|<\epsilon n$,
3. $|V_1|=|V_2|=\cdots =|V_k|$,
4. $\epsilon k^2$ kivételével minden $(V_i,V_j)$ pár $\epsilon$-reguláris.

Bizonyítása

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

$\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 $\text{ind}(P)\le \frac{1}{2}$. Ezután belátjuk, hogy ha egy $P=(V_0,V_1,\dots ,V_k)$ partícióban több, mint $\epsilon k^2$ pár nem $\epsilon$-reguláris, akkor van egy P-t finomító Q partíció legfeljebb $1+k{4}^k$ részre, amire

$\text{ind}(Q)\ge \text{ind}(P)+\frac{{\epsilon }^5}{20}$

teljesül. Ezután legfeljebb $10/{\epsilon }^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 $f(10/{\epsilon }^5)$, ahol az f függvényt az $f(0)=m$, $f(t+1)=1+f(t)4^{f(t)}$ rekurzióval definiáljuk.

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