Szubjektiv megjegyzesek a szeminariumhoz
A kozonseges grafokra a regularitasi lemmanak nagyon sok alkalmazasa van,
a hipergraph lemmanak sokkal kevesebb. Ennek reszben az az oka, hogy a
hipergraf problemak sokkal bonyolultabbak, mint a kozonseges grafproblemak,
reszben az, hogy maga a lemma is sokszorta bonyolultabb.
Ha a regularitasi lemma megvan, kozonseges grafoknal az sokszor alkalmas
arra is, hogy bizonyos tipusu reszgrafokat megszamoljunk. Hipergrafoknal az
eredeti legegyszerubb lemma erre teljesen alkalmatlan volt, a bonyolultabb
verzio (Frankl-Rodl / Chung) viszont mar alkalmas, de nagyon nehez meg a
kimondasa is: Endrenek lenyegeben a teljes masodik eloadasat elvitte.
A hipergrafoknal a reszgraf-szamolas elvalik: igy a regularity lemma-t es
a counting lemmat kulon szoktak kimondani, bizonyitani.
Endre azt igerte, hogy ismerteti a Rodl es tanitvanyai verziojat, illetve
a Gowers verziot. Az utobbiban a ket lemma kozelebb lesz egymashoz, de a
Regularity lemma bizonyitasa nehezebb lesz.
Letezik meg egy "removal lemma" is, ez is egyszeru kozonseges grafokra,
de sokaig rejtve maradt. Ennek lenyege az, hany elet kell elhagyni, bizonyos
tipusu reszrafok lerombolasahoz.
Ezt hasznalta Furedi a Plesnik-Simon-Murty sejtes
bizonyitasara, es manapsag egy egesz elmelet van lenyegeben erre bazirozva:
a graph-property-testing.
(Alon, Krivelevich, Sudakov es meg sokan masok)
A graph property testing bizonyos korulmenyek kozott lenyegeben ekvivalens a
regularitasi lemma alkalmazasaval.
Hipergrafokra meg nem nagyon lattam graph property testing-et.
A graph property testing Lovasz es Szegedy munkaiban is elojon (egyebek
kozott), amelyik egyebkent kapcsolodik nemileg a homomorphism modszerhez.