Szemerédi-féle regularitási lemma

A Wikipédiából, a szabad enciklopédiából

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 1978-as 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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.


Általánosításai[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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", Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica 27: 199–245, <http://matwbn.icm.edu.pl/tresc.php?wyd=6&tom=27>
  3. Szemerédi, Endre (1978), "Regular partitions of graphs", Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), vol. 260, Colloq. Internat. CNRS, Paris: CNRS, pp. 399–401
  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.

További információk[szerkesztés | forrásszöveg szerkesztése]