Topological combinatorics




Instructor: Frédéric Meunier


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.


Outline:
  • 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
  • Applications.
    • 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
    • Some PPAD-complete problems



Bibliography:
  • 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: Sperners lemma in fair division, Amer. Math. Monthly, 1999.