Úvod do extremální teorie grafů

Čtvrtek 10:40 na chodbě ve 2. patře.

Plan
  • 6.10.: Introduction and revision (Turan's theorem, basic results regarding ex(n;F) for bipartite F). Česky, English.
  • 13.10.: Erdös-Stone theorem. Česky, English. Ex(Kt+1,s, n) for s>t!. Česky, English.
  • 20.10.: Dependent random choice. Česky, English.
  • 27.10.: Even cycles. Česky, English.
  • 3.11.: Stability for Erdös-Stone theorem. Česky, English.
  • 10.11.: Applications of stability: Exact extremal function for graphs with an extremal edge and for kKr+1. Česky, English.
  • 24.11.: Introduction to hypergraph extremal theory, density of hypergraphs avoiding the Fano plane. English. The lecture is based on this paper.
  • 1.12.: Density, convergence and limits. English.
  • 8.12.: The method of flag algebras. English. The application is based on this paper.
  • 15.12.: Supersaturation. Czech, English.
  • 22.12.: Turán problem for hypergraphs. English.
  • 5.1.: Reserve
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