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 szerkesztés

Egy   gráf esetén, ha  , jelölje e(A,B) az A és B közötti élek számát,  .

Ha  , akkor (A,B) pár  -reguláris, ha minden  ,   esetén, ha   és  , akkor   teljesül.

A regularitási lemma állítása szerkesztés

Ha adott az   szám és   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  , akkor V particionálható a   halmazokra, hogy

  1.  ,
  2.  ,
  3.  ,
  4.   kivételével minden   pár  -reguláris.

Bizonyítása szerkesztés

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

 

mennyiséget. Erre mindig teljesül  . Ezután belátjuk, hogy ha egy   partícióban több, mint   pár nem  -reguláris, akkor van egy P-t finomító Q partíció legfeljebb   részre, amire

 

teljesül. Ezután legfeljebb   lépésben eljutunk egy, a lemma állítását kielégítő partícióhoz, ahol a részek száma legfeljebb  , ahol az f függvényt az  ,   rekurzióval definiáljuk.


Általánosításai szerkesztés

Jegyzetek szerkesztés

  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.

További információk szerkesztés