Vyuka - Teorie grafovych minoru

Obsah prednasky:

Popis struktury grafu bez zakazaneho minoru a teoreticke a algoritmicke aplikace tohoto popisu. Hlavni myslenky a metody dukazu (tangle, stromova sirka a zdi; vlastnosti grafu na plochach; linkovanost) a jejich dalsi vyuziti. Pripadne dle zajmu novejsi vysledky (struktura grafu se zakazanym podrozdelenim, strukturalni veta pro matroidy, ...).

Kdy a kde:

ctvrtek 15:40 S6
cviceni (obcasne dle dohody): pondeli 10:40

Odprednesena latka:

Datum	Obsah prednasky	Zdroje
25.2.	Opakovani, definice, hlavni myslenky a ingredience dukazu strukturalni vety.	Poznamky k WQO
3.3.	Stromova sirka a tangle.	Minory X; poznamky; Priklady ke cviceni
10.3.	Velka stromova sirka vynucuje velkou zed.	Highly Connected Sets and the Excluded Grid Theorem; poznamky; Improved Bounds for the Flat Wall Theorem
17.3.	Tangle a metrika na plochach.	Minory XI, XII; Shrnuti
21.3.	Plochy a linkovani.	Minory VI a VII; Shrnuti a priklad ke cviceni
31.3.	Two Short Proofs Concerning Tree-Decompositions (referat)	Clanek
14.4.	2-linkage a jejich zobecneni (transakce).	Minory IX
21.4.	Rozsirovani vnoreni.	Minory XIV a XV
28.4.	Strukturalni veta.	Minory XVI, plan utoku.
5.5.	Testovani existence minoru.	Minory XIII,XXI,XXII
12.5.	Stromove rozklady a dobre usporadani.	Minory IV
19.5.	Plochy a dobre usporadani.	???
26.5.	Wagnerova hypoteza.	Minory X, XX

Doporucena literatura:

N. Robertson, P. Seymour: Graph Minors. I. - XXIII.
N. Robertson, P. Seymour, R. Thomas: Quickly Excluding a Planar Graph, J. Comb. Theory, Ser. B (1994), 323-348.
C. Thomassen: A simpler proof of the excluded minor theorem for higher surfaces, J.Combinatorial Theory B 70 (1997), 306-311.
K. Kawarabayashi, P. Wollan: A simpler algorithm and shorter proof for the graph minor decomposition, STOC 2011, 451-458.
M. Grohe, K. Kawarabayashi, D. Marx, P. Wollan: Finding topological subgraphs is fixed-parameter tractable, STOC 2011, 479-488.
R. Diestel, T. Jensen, K. Gorbunov, C. Thomassen: Highly Connected Sets and the Excluded Grid Theorem, J. Comb. Theory, Ser. B (1999), 61-73.
Julia Chuzhoy: Improved Bounds for the Flat Wall Theorem. SODA 2015: 256-275.