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

Speaker
Dr. Shira Zerbib,University of Michigan and MSRI
Date
10/12/2017 - 13:00 - 12:00Add to Calendar 2017-12-10 12:00:00 2017-12-10 13:00:00 Colorful coverings of polytopes -- the topological truth behind different colorful phenomena he topological KKMS Theorem is a powerful extension of 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 celebrated 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 collections of d-interval families (namely, d+1 families of sets in R, every set being a union of d intervals); this generalizes 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. Colloquium room, Mathematics Dept.,building 216 אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Colloquium room, Mathematics Dept.,building 216
Abstract

he topological KKMS Theorem is a powerful extension of 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 celebrated
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 collections of d-interval families (namely, d+1 families of sets in
R, every set being a union of d intervals); this generalizes 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.

תאריך עדכון אחרון : 08/12/2017