Ú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)
- Opakování: Mantelova a Turánova věta. Hypergrafy: Erdos-Ko-Rado.
- 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.
- Dependent random choice: Úvod do metody, aplikace na Ex(G,n) pro bipartitní G.
- Sudé cykly: Přesnější výsledky pro Ex(C_{2k}, n), Bondy-Simonovitsova věta.
- Stabilita: Přesný výsledek pro grafy s kritickou hranou.
- Supersaturace: Růst počtu výskytů nad dolní mezí.
- Regularity lemma: Formulace a aplikace.
- Asymptotické výsledky: Hustoty podgrafů a homomorfismů, konvergence a limity.
- Flag algebry: Úvod do metody, aplikace na jednoduché příklady.
Další materiály a zdroje
- Béla Bollobás, Extremal graph theory
- Stasys Jukna, Extremal Combinatorics. With applications in computer science
- Přednášky Davida Conlona
- Přednášky Andrew Thomasona
- Přednášky Asaf Shapira
- Přednášky Ryana Martina
- János Kollár, Lajos Rónyai, Tibor Szabó: Norm-graphs and bipartite Turán numbers - Ex(Kt,s, n) pro s>t!.
- Jacob Fox, Benny Sudakov: Dependent Random Choice