Úvod do extremální teorie grafů

On Fridays 10:40 on Zoom, meeting id 939 2648 1221 (e-mail me to obtain the password).

Plan
  • 9.10.: Introduction and revision (Turan's theorem, basic results regarding ex(n;F) for bipartite F). Česky, English.
  • 16.10.: Erdös-Stone theorem. Česky, English. Ex(Kt+1,s, n) for s>t!. Česky, English.
  • 23.10.: Dependent random choice. Česky, English.
  • 30.10.: Even cycles. Česky, English.
  • 6.11.: Stability for Erdös-Stone theorem. Česky, English.
  • 13.11.: Applications of stability: Exact extremal function for graphs with an extremal edge and for kKr+1. Česky, English.
  • 20.11.: Introduction to hypergraph extremal theory, density of hypergraphs avoiding the Fano plane. English. The lecture is based on this paper.
  • 27.11.: Density, convergence and limits. English.
  • 4.12.: The method of flag algebras. English. The application is based on this paper.
  • 8.12.: A guest lecture by Jan Volec on practical aspects of the flag algebra method.
  • 11.12.: Supersaturation. Czech, English.
  • 8.1.: Turán problem for hypergraphs. English.
Obsah přednášek (rok 2016)
  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