We prove three results about colorings of the simplex reminiscent of Sperner’s Lemma, with applications in hardness of approximation and fair division.
First, we prove a coloring lemma conjectured by Ene and Vondrák [2014]: Let
\begin{align*} V_{k,q} &= \bigl\{ \mathbf{v}\in \mathbb{Z}_+^k: \textstyle\sum_{i=1}^k v_i = q \bigr\} \quad\text{and}\\ E_{k,q} &= \bigl\{ \{\mathbf{a} + \mathbf{e}_1,\mathbf{a} + \mathbf{e}_2,\dots, \mathbf{a} + \mathbf{e}_k\}\,:\,\mathbf{a}\in \mathbb{Z}_+^k, \textstyle\sum_{i=1}^k a_i = q-1 \bigr\} . \end{align*}
Then for every Sperner-admissible labeling (\( \ell: V_{k,q} \to [k] \) such that \( v_{\ell(\mathbf{v})} > 0 \) for each \( \mathbf{v}\in V_{k,q} \)), there are at least \( {q+k-3\choose k-2} \) non-monochromatic hyperedges in \( E_{k,q} \). This implies an optimal Unique-Games hardness of \( (k{-}1{-}\epsilon) \)-approximation for the Hypergraph Labeling with Color Lists problem [Chekuri and Ene 2011]: Given a \( k \)-uniform hypergraph \( H = (V,E) \) with color lists \( L(v)\subseteq [k] \), \( \forall v\in V \), find a labeling \( \ell(v)\in L(v) \) that minimizes the number of non-monochromatic hyperedges. We also show that a \( (k{-}1) \)-approximation can be achieved.
Second, we show that in contrast to Sperner’s Lemma, there is a Sperner-admissible labeling of \( V_{k,q} \) such that every hyperedge in \( E_{k,q} \) contains at most 4 colors. We present an interpretation of this statement in the context of fair division: There is a preference function on
\[ \Delta_{k,q} = \bigl\{ \mathbf{x}\in\mathbb{R}_+^k: \textstyle\sum_{i=}^k x_i = q \bigr\} \]
such that for any division of \( q \) units of a resource, \( (x_1,x_2,\dots \), \( x_k)\in\Delta_{k,q} \) such that
\[ \textstyle\sum_{i=1}^k \lfloor x_i \rfloor = q-1 ,\]
at most 4 players out of \( k \) are satisfied.
Third, we prove that there are subdivisions of the simplex with a fractional labeling (analogous to a fractional solution for Min-CSP problems) such that every hyperedge in the subdivision uses only labelings with 1 or 2 colors. This means that a natural LP cannot distinguish instances of Hypergraph Labeling with Color Lists that can be labeled so that every hyperedge uses at most 2 colors, and instances that must have a rainbow hyperedge. We prove that this problem is indeed NP-hard for \( k = 3 \).
