Tárgy neve: Extremális gráfelmélet (MSc)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
Mantel tétel, Turán tétel, Erdős-Stone-Simonovits tétel, Zarankiewicz probléma, maximális élszámú gráfok, amik nem tartalmaznak adott méretű teljes részgráfot/teljes páros részgráfot. Általánosabb Turán típusú kérdések egyéb kizárt gráfok (pl.: fák, körök) esetén, illetve hipergráfokon. Pánciklikus gráfok, Bondy tétel, Moon-Moser egyenlőtlenségek. Szaturálási kérdések, Kászonyi-Tuza tétel. Ramsey tétel, Ramsey típusú kérdések gráfokon. Szemerédi regularitási lemma változatai, elhagyási lemma, számlálási lemma, beágyazási lemma és ezek alkalmazásai, Roth tétele. Pszeudo-véletlen gráfok, Chung-Graham-Wilson tétel. További nevezetes módszerek extremális kérdésekkel kapcsolatban: Véletlen módszer néhány alkalmazása, Lovász lokál lemma. Kombinatorikus nullhelytétel és néhány alkalmazása. A Kneser sejtés bizonyítása topologikus eszközökkel (Borsuk-Ulam tétel).

Előadás kódja: MMNM56E, óraszám: 3, kredit: 4