A Sparse colorful polytopal KKM Theorem

Abstract

Recently Soberón proved a far-reaching generalization of the colorful KKM Theorem due to Gale: let $n\ge k$, and assume that a family of closed sets $(A_j^i\mid i\in [n],j\in [k])$ has the property that for every $I\in \left(\genfrac{}{}{0ex}{}{[n]}{n-k+1}\right)$, the family $({\bigcup }_{i\in I}{A}_1^i,\dots ,{\bigcup }_{i\in I}{A}_k^i)$ is a KKM cover of the $(k-1)$-dimensional simplex ${\Delta }^{k-1}$; then there is an injection $\pi :[k]\to [n]$ so that ${\bigcap }_{i=1}^k{A}_i^{\pi (i)}\ne \varnothing$. We prove a polytopal generalization of this result, answering a question of Soberón in the same note. We also discuss applications of our theorem to fair division of multiple cakes, $d$-interval piercing, and a generalization of the colorful Carathéodory theorem.