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 1978-as 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 $\varepsilon>0$, akkor (A,B) pár $\varepsilon$-reguláris, ha minden $A'\subseteq A$, $B'\subseteq B$ esetén, ha $|A'|>\varepsilon |A|$ és $|B'|>\varepsilon |B|$, akkor $|d(A',B')-d(A,B)|<\varepsilon$ teljesül.

A regularitási lemma állítása

Ha adott az $\varepsilon>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|\geq N$, akkor V particionálható a $V_0,V_1,\dots,V_k$ halmazokra, hogy

1. $m\leq k\leq M$,
2. $|V_0|<\varepsilon n$,
3. $|V_1|=|V_2|=\cdots=|V_k|$,
4. $\varepsilon k^2$ kivételével minden $(V_i,V_j)$ pár $\varepsilon$-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^{k}_{i=1}\sum^{k}_{j=i+1}d^2(V_i,V_j)$

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

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

teljesül. Ezután legfeljebb $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 $f(10/\varepsilon^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