# Sperner's colorings, hypergraph labeling problems and fair division

## Abstract

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 [5]: Let Vk, q={v ∈ ℤk)+:σ ki=1vi=q} and Ek, q={{a + e1, a + e2, ⋯, a + ek}: a ∈ℤk+, σki-1ai=q-1}. Then for ev-ery Sperner-admissible labeling (ℓ: Vk, q → [k] such that vℓ (v) > 0 for each v ∈Vk, q), there are at least (q+k-3k-2) monochromatic hyperedges in Ek, q. This implies an optimal Unique-Games hardness of (k-1-∈)-approximation for the Hypergraph Labeling with Color Lists problem [2]: Given a A;-uniform hypergraph H=(V, E) with color lists L (v) ⊆ [k] ∀v ∈V, find a labeling ℓ (v) ∈L (v) that minimizes the number of non-monochromatic hyperedges. We also show that a (k-l)-approximation can be achieved. Second, we show that in contrast to Sperner's Lemma, there is a Sperner-admissible labeling of Vk, q such that every hy-peredge in Ek, 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 Δk, q={x ∈ℝk+: σ=1xi=q} such that for any division of q units of a resource, (xi, x2, ⋯ xk) ∈δk, q such that σki=1 ⌊xi⌋=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.