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.