Teorie grafových minorů

Rozvržení:

  • Přednáška: pondělí 14:00 v mé kanceláři (323).
  • Cvičení: formou kontrolované četby.

Plán přednášek
  1. Opakování: plochy, stromové rozklady, bramble, tangle.
  2. Tangle, metrika a minory na plochách.
    • Cvičení: linkování na disku a cylindru.
  3. (2 přednášky) Formulace strukturální věty. Aplikace: Rozklad na grafy omezené stromové šířky.
    • Cvičení: Algoritmické aplikace, další rozklady.
  4. Zesílení strukturální věty. Aplikace: Bipartitní minory v grafech velké souvislosti.
    • Cvičení: Linkovanost v grafech lineárně velké souvislosti.
  5. Strukturální věta pro zakázaná podrozdělení, testování izomorfismu.
    • Cvičení: Izomorfismus grafů se zakázanými minory.
  6. Testování existence minoru a podrozdělení.
    • Cvičení: Testování existence nakreslení na plochu.
  7. Hadwigerova hypotéza (Souvislost minimálního protipříkladu, podmíněný algoritmus pro barvení lineárním počtem barev).
    • Cvičení: Zlomková verze Hadwigerovy hypotézy.
  8. Velké mřížky a sublineární řezy v grafech se zakázanými minory.
    • Cvičení: Bidimensionalita.
  9. (2 přednášky) Věta o polynomiálně velké mřížce.
    • Cvičení: WQO pro grafy omezené stromové šířky.
  10. Rezerva.
Obsah přednášek (v minulých letech)
  1. Opakování, definice, hlavní myšlenky a ingredience důkazu strukturální věty.
  2. Stromová šířka a tangle.
  3. Velká stromová šířka vynucuje velkou zeď.
  4. Tangle a metrika na plochách.
  5. Plochy a linkování.
  6. Two Short Proofs Concerning Tree-Decompositions
  7. 2-linkage a jejich zobecnění (transakce).
  8. Rozšiřování vnoření.
  9. Strukturální věta.
  10. Testování existence minoru.
  11. Stromové rozklady a dobré uspořádáni.
  12. Plochy a dobré uspořádání.
  13. Wagnerova hypotéza.
Další materiály a zdroje

Doporučená 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.

Další zdroje