All Articles

Postdoctoral T.H. Hildebrandt Assistant Professor
Department of Mathematics
University of Michigan

Colorful phenomena in discrete geometry and combinatorics via topological methods

We will discuss two recent topological results and their applications to several different problems in discrete geometry and combinatorics involving colorful settings.

The first result is a polytopal-colorful generalization of the topological KKMS theorem due to Shapley. We apply this theorem to prove a new colorful extension of the d-interval theorem of Tardos and Kaiser, as well as to provide a new proof to the celebrated colorful Caratheodory theorem due to Barany. Our theorem can be also applied to questions regarding fair-division of goods (e.g., multiple cakes) among a set of players. This is a joint work with Florian Frick.

The second result is a new topological lemma that is reminiscent of Sperner’s lemma: instead of restricting the labels that can appear on each face of the simplex, our lemma considers labelings that enjoy a certain  symmetry on the boundary of the simplex. We apply this to prove that the well-known envy-free division theorem of a cake is true even if the players are not assumed to refer non-empty pieces, whenever the number of players is prime or equal to 4.  This is joint with Frederic Meunier.