Leírás
Regularitási módszernek a Regularitási lemma és a Blow-up lemma (beágyazó lemma) együttes használatát szokás hívni. Rendkívül hatékony extremális gráfelméleti kérdésekben, több száz tétel bizonyításának adja a gerincét. Hátránya, hogy a Regularitási lemma csak "csillagászati" méretű gráfokra hasznos igazán.
Az előadásban egy olyan módszert láthatunk, ami a Regularitási lemmát képes kiváltani bizonyos esetekben, úgy, hogy a Blow-up lemma (mely kis gráfokra is érvényes) továbbra is használható legyen. A módszer működésének demonstrálására egy fa beágyazási tétel bizonyítását tekintjük: ha az n csúcsú G gráf minimális foka legalább n/2 +\epsilon n valamely \epsilon >0-ra, és T egy n csúcsú, korlátos fokú fa, n elég nagy, akkor T feszítőfája G-nek.
Ez egy ismert tétel. Bollobás sejtése volt 1978-ból, kb. 20 évre rá bizonyította Komlós, Sárközy és Szemerédi a Regularitási lemma használatával. 2010-ben beláttuk egy Nagy-György Judittal, Ian Levittel és Szemerédi Endrével közös cikkben, már a lemma használata nélkül, viszont így jóval bonyolultabban a tétel első bizonyításánál.
A legújabb bizonyítás előnye, hogy a Regularitási módszer több eleme is átvihető, de "kis" gráfokra is működik. Újdonság még emellett, hogy egy erősebb, ún. stabilitási változatot bizonyítunk: ha G nincs nagyon közel két extremális esethez (két diszjunkt klikk uniója ill. teljes páros gráf), akkor n/2-\epsilon n -es minimális fokszám is elegendően nagy a tartalmazáshoz.