Instructor: Frédéric Meunier, Matej Stehlik
Prerequisites: Notions of graph theory, topology, and complexity theory.
Objective: Since a breakthrough result by Lovász in 1979, topology has been successfully applied to combinatorics
and has provided many neat and striking results for which no alternate proof is known. This cours aims at introducing this active area to the students and at presenting
its classical results as well as its main current challenges.
- Topological tools.
- Sperner's lemma, the Brouwer fixed point theorem, and related results
- Self-maps and surjectivity
- Tucker's lemma, the Borsuk-Ulam theorem, and related results
- Envy-free and fair divisions
- Covers and matchings for d-intervals
- Colorful independent sets
- Topological lower bounds on the chromatic number
- Computational considerations.
- Path-following methods
- The PPAD and PPA classes
Exam: 1:30pm-4:30pm, Thursday January 16.
Sessions: 1:30pm-3pm and 3:15pm-4:45pm on the following Thursdays
- October 17, 24.
- November 7, 14, 21, 28.
5, 12, 19.
- January 9.
- M. De Longueville, A course in topological combinatorics, Springer, 2012.
- X. Deng, Q. Qi, and A. Saberi, Algorithmic solutions for envy-free cake cutting, Operations Research, 2012.
- J. Matoušek, Using the Borsuk-Ulam theorem, Springer, 2003.
- J. Matoušek and G. Ziegler, Topological lower bounds for the chromatic number: A hierarchy, Jahresbericht der Deutschen Mathematiker-Vereinigung, 2004.
- D. Pálvölgyi, Combinatorial Necklace Splitting, The Electronic Journal of Combinatorics, 2009.
- C. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. Systems Sci. , 1994.
- F. Su, Rental harmony: Sperner's lemma in fair division, Amer. Math. Monthly, 1999.