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 $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

$m\leq k\leq M$ ,
$|V_{0}|<\varepsilon n$ ,
$|V_{1}|=|V_{2}|=\cdots =|V_{k}|$ ,
$\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 _{i=1}^{k}\sum _{j=i+1}^{k}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.

Általánosításai

Jegyzetek

↑ 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 (1975). „On sets of integers containing no k elements in arithmetic progression” (angol nyelven) (PDF). Acta Arithmetica 27 (1), 199–245. o, Kiadó: Institute of Mathematics of the Polish Academy of Sciences. MR 0369312.
↑ Szemerédi, Endre. Regular partitions of graphs, Problèmes combinatoires et théorie des graphes, Colloques internationaux du Centre national de la recherche scientifique (no. 260) (angol nyelven). Paris: Francia Nemzeti Tudományos Kutatási Központ (CNRS), 399–401. o.. MR 540024 [1975] (1978). ISBN 978-2222020707
↑ 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
↑ W. 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.

További információk

Matematikaportál • összefoglaló, színes tartalomajánló lap

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

[2] Szemerédi, Endre (1975). „On sets of integers containing no k elements in arithmetic progression” (angol nyelven) (PDF). Acta Arithmetica 27 (1), 199–245. o, Kiadó: Institute of Mathematics of the Polish Academy of Sciences. MR 0369312.

[3] Szemerédi, Endre. Regular partitions of graphs, Problèmes combinatoires et théorie des graphes, Colloques internationaux du Centre national de la recherche scientifique (no. 260) (angol nyelven). Paris: Francia Nemzeti Tudományos Kutatási Központ (CNRS), 399–401. o.. MR 540024 [1975] (1978). ISBN 978-2222020707

[4] P. Frankl, V. Rödl: Extremal problems on set systems, Random Structures & Algorithms, 20 (2002), 131–164.

[5] V. Rödl, J. Skokan: Regularity lemma for uniform hypergraphs, Random Structures & Algorithms, 25 (2004), 1–42.

[6] B. Nagle, V. Rödl, M. Schacht: The Counting Lemma for regular k-uniform hypergraphs, Random Structures & Algorithms, 28 (2006), 113–179

[7] W. T. Gowers: Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, Combinatorics, Probability and Computing, 15 (2006), 143–184.

[8] W. T. Gowers: Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, 166 (2007), 897–946.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]