Series

We plan the following monothematic series of talks for the Spring School:

• Inifinite graphs

  • Introduction (source: Diestel, Graph Theory; chapter 8 – Infinite graphs)

  • Diestel: Locally finite graphs with ends: A topological approach, I. Basic theory

  • Diestel: Locally finite graphs with ends: A topological approach, II. Applications

  • Stein: Extremal infinite graph theory

  Contact person: Jan Mazák
  
  

• Combinatorial optimization

  This series will extend what is commonly taught in lectures at Charles University. The main source for all talks is the monograph Combinatorial Optimization by A. Schrijver.

  • The dimension of the perfect matching polytope and the perfect matching lattice (chapters 37 and 38)

  • Submodular functions and polymatroids (chapter 44)

  • Submodular function minimization (chapter 45)

  • Polymatroid intersection and algorithmic version (chapters 46 and 47)

  Contact person: Dan Král
  
  

Other talks

• Kreutzer, Tazari: Lower Bounds for the Complexity of Monadic Second-Order Logic (reserved: Jakub Gajarský)

• Scott: Szemerédi's Regularity Lemma for matrices and sparse graph (reserved: Pavel Klavík)

• Datta, Prakriya: Planarity Testing Revisited (reserved: Michal Hanzlík)

• Kawarabayashi, Thorup: Minimum k-way cut of bounded size is fixed-parameter tractable (reserved: Matěj Klusáček)

• King, Reed: Asymptotics of the chromatic number for quasi-line graphs (reserved: Barbora Candráková)

• Kammer, Tholey: Approximate Tree Decompositions of Planar Graphs in Linear Time (reserved: Tomáš Gavenčiak)

• Kreutzer, Tazari: Directed Nowhere Dense Classes of Graphs (reserved: Vojta Tůma)

• Fox, Loh: On a problem of Erdős and Rothschild on edges in triangles (reserved: Jarett Schwarz)

• Li, Szegedy: On the logarithimic calculus and Sidorenko's conjecture (reserved: Lukáš Mach)

• Kratsch: Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem (reserved: Markus Dregi)

• Barvinok: A bound for the number of vertices of a polytope with applications (reserved: Robert Lukotka)

• Berry, McDiarmid, Reed: Connectivity for bridge-addable monotone graph classes

• Gaspers, Szeider: Backdoors to Acyclic SAT

• Krivelevich, Sudakov: The phase transition in random graphs - a simple proof (reserved: Jan Volec)

• Demaine, Hajiaghayi, Mohar: Approximation Algorithms via Contraction Decomposition

• Kang, Lovász, Müller, Scheinerman: Dot Product Representations of Planar Grap (reserved: Jaroslav Hančl)

• Fomin, Golovach, Thilikos: Contraction Obstructions for Treewidth (reserved: Remy Belmonte)

• Kakimura, Kawarabayashi, Marx: Packing Cycles through Prescribed Vertices (reserved: Reza Saeidinvar)

• Downey, Fellows, Vardy, Whittle: The Parameterized Complexity of Some Fundamental Problems in Coding Theory (reserved: Tereza Klimošová)

• Norine: Turán Graphs and the Number of Colorings (reserved: Roman Glebov)

If you have a problem with downloading some article, feel free to ask for a copy by email.