Speaker: Shira Zerbib Gelaki (MSRI, University of Michigan)

Title: Colorful coverings of polytopes -- the hidden topological truth behind different colorful phenomena

Abstract:

The topological KKMS Theorem is a powerful extension of the Brouwer's Fixed-Point Theorem, which was proved by Shapley in 1973 in the context of

game theory.

We prove a colorful and polytopal generalization of the KKMS Theorem, and show that our theorem implies some seemingly unrelated results in

discrete geometry and combinatorics involving colorful settings.

For example, we apply our theorem to provide a new proof of the Colorful Caratheodory Theorem due to Barany, which asserts that if 0 is in the

convex hull of n+1 sets of points in R^n, then there exists a colorful selection of points, one from each set, containing 0 in its convex hull. We

further apply our theorem to obtain an upper bound on the piercing numbers in colorful d-interval families, extending results of Tardos, Kaiser

and Alon for the non-colored case. Finally, we apply our theorem to questions regarding envy-free fair division of goods (e.g., cakes) among a set

of players.

Joint with Florian Frick.

Title: Colorful coverings of polytopes -- the hidden topological truth behind different colorful phenomena

Abstract:

The topological KKMS Theorem is a powerful extension of the Brouwer's Fixed-Point Theorem, which was proved by Shapley in 1973 in the context of

game theory.

We prove a colorful and polytopal generalization of the KKMS Theorem, and show that our theorem implies some seemingly unrelated results in

discrete geometry and combinatorics involving colorful settings.

For example, we apply our theorem to provide a new proof of the Colorful Caratheodory Theorem due to Barany, which asserts that if 0 is in the

convex hull of n+1 sets of points in R^n, then there exists a colorful selection of points, one from each set, containing 0 in its convex hull. We

further apply our theorem to obtain an upper bound on the piercing numbers in colorful d-interval families, extending results of Tardos, Kaiser

and Alon for the non-colored case. Finally, we apply our theorem to questions regarding envy-free fair division of goods (e.g., cakes) among a set

of players.

Joint with Florian Frick.

## Date:

Thu, 07/12/2017 - 12:00 to 13:00

## Location:

Room 101 in Sprinzak