This course is discontinued


This course will be an introduction to combinatorial optimization and discrete geometry, with a strong emphasis on polyhedral combinatorics. Lectures will mainly be based on the following texts: 

Lectures on Polytopes by Günter Ziegler.

- A Course in Combinatorial Optimization by Alexander Schrijver.

- An Introduction to Convexity by Geir Dahl.

The preliminary syllabus is as follows. Minor changes can occur based on the audience interests.

  • Introduction, optimization and convexity.
  • Some graph algorithms: minimum spanning trees, shortest paths, network flows.
  • Polyhedral basics: Fourier-Motzkin elimination, Farkas lemma, recession cones, Caratheodory's theorem.
  • Linear programming and duality, polyhedral approaches to graph algorithms, max-flow min-cut theorem, matchings in bipartite graphs.
  • Integrality of polyhedra, total unimodularity, transportation polytopes.
  • Faces of polytopes, polytope duality.
  • Graphs of polytopes, Hirsh conjecture, Balinski's theorem, Steinitz' theorem.
  • Triangulations of polytopes, Catalan numbers, secondary polytopes.
  • Euler's theorem, shellability, f and h vectors, g-theorem.
Published June 3, 2016 2:17 PM - Last modified June 3, 2016 2:58 PM