Úvod do extremální teorie grafů

Rozvržení: středa 15:40 v S9.

Plán přednášek
  • 5.10.: Úvod, opakování.
  • 12.10.: Erdös-Stoneova věta, základní výsledky o Ex(G,n) pro bipartitní G.
  • 19.10.: Ex(Kt,s, n) pro s>t! (přednese Jan Hladký).
  • 26.10.: odpadá
  • 2.11.: Dependent random choice.
  • 9.11.: Sudé cykly.
  • 16.11.: Stabilita Erdös-Stoneova odhadu.
  • 23.11.: odpadá (DoD).
  • 30.11.: Přesný odhad extremální funkce pro grafy s kritickou hranou (aplikace stability).
  • 7.12.: Úvod do extremálních výsledků pro hypergrafy. Hustota hypergrafů bez Fanovy roviny (asymptoticky a přesný odhad -- bez důkazu stability).
  • 14.12.: Hustoty, konvergence a limity.
  • 21.12.: Flag algebry.
  • 4.1.: Regularity lemma - opakování, aplikace (stabilita a supersaturace v Erdös-Stoneově odhadu).
  • 11.1.: Supersaturace.
Obsah přednášek
  1. Opakování: Mantelova a Turánova věta. Hypergrafy: Erdos-Ko-Rado.
  2. Rozšíření Turánovy věty: Erdös-Stoneova věta (důkaz bez regularity lemmatu), opakování a základní výsledky o Ex(G,n) pro bipartitní G.
  3. Dependent random choice: Úvod do metody, aplikace na Ex(G,n) pro bipartitní G.
  4. Sudé cykly: Přesnější výsledky pro Ex(C_{2k}, n), Bondy-Simonovitsova věta.
  5. Stabilita: Přesný výsledek pro grafy s kritickou hranou.
  6. Supersaturace: Růst počtu výskytů nad dolní mezí.
  7. Regularity lemma: Formulace a aplikace.
  8. Asymptotické výsledky: Hustoty podgrafů a homomorfismů, konvergence a limity.
  9. Flag algebry: Úvod do metody, aplikace na jednoduché příklady.
Další materiály a zdroje