Discrete topology and geometry, and applications

Instructors. Xavier Goaoc (goaoc@univ-mlv.fr) and Frédéric Meunier (frederic.meunier@enpc.fr).

Topic. This course will cover some discrete theorems in topology (Sperner and Tucker) and geometry (Helly and Carathéodory) as well as several of their applications. We will illustrate how these theorems offer elementary gateways to a diversity of results in game theory and fair division, in graph theory, in optimization and in geometric data analysis.

Ressource. The lecture will build on the survey The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg by De Loera, Goaoc, Meunier and Mustafa.

Schedule.

Thursday 24th of May	10:00-12:00	room F108 (Coriolis)	(Frédéric)	Sperner: dividing a cake fairly
Thursday 31st of May	10:00-12:00	room F108 (Coriolis)	(Xavier)	Caratheodory: pivoting in linear programming
Wednesday 6th of June	10:00-12:00	room F103 (Coriolis)	(Xavier)	More pivoting: Nash equilibria and the Lemke-Howson algorithm
Thursday 14th of June	10:00-12:00	room F108 (Coriolis)	(Frédéric)	Tucker: dividing necklaces and sandwiches
Thursday 21th of June	10:00-12:00	room F108 (Coriolis)	(Frédéric)	Tucker: coloring graphs
Thursday 28th of June	10:00-12:00	room Seminar room (Coriolis)	(Xavier)	Helly: sampling in linear programming (slides)

Pre-requisite. We will assume a general background in mathematics (continuity, vector spaces, etc.).