Introduction to the extremal graph theory

Tuesdays 10:40–12:10 in the 2nd floor corridor.

Plan
  • 1.10. (M.T.): Introduction and revision (Turan's theorem, basic results regarding ex(n;F) for bipartite F). Česky, English.
  • 8.10. (Z.D.): Erdös-Stone theorem. Česky, English.
  • 15.10. (Z.D.): Extremal function for bipartite graphs, Ex(Kt+1,s, n) for s>t!. Česky, English.
  • 22.10. (M.T.): Dependent random choice. Česky, English.
  • 29.10. (M.T.): Even cycles. Česky, English.
  • 5.11.: Cancelled (sporting day).
  • 12.11. (Z.D.): Stability for Erdös-Stone theorem. Česky, English.
  • 19.11. (Z.D.): Applications of stability: Exact extremal function for graphs with an extremal edge and for kKr+1. Česky, English.
  • 26.11. (Z.D.): Density, convergence and limits. English.
  • 3.12. (Z.D.): The method of flag algebras. English. The application is based on this paper.
  • 10.12.: (M.T.): Introduction to hypergraph extremal theory, density of hypergraphs avoiding the Fano plane. English. The lecture is based on this paper.
  • 17.12.: (M.T.) Turán problem for hypergraphs. English.
  • 7.1.:(M.T.) Supersaturation. Czech, 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