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 V_(k,q) = {v ∈ Z_+~k : Σ_(i=1)~k v_i = q} and E_(k,q) = {{a + e_1, a + e_2,..., a + e_k} : a ∈ Z_+~k, Σ_(i=1)~k a_i = q - 1}. Then for every Sperner-admissible labeling (l : V_(k,q) → [k] such that v_(l(v)) > 0 for each v ∈ V_(k,q)), there are at least ({sup}(q+k-3){down}(k-2)) non-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 k-uniform hypergraph H = (V;E) with color lists L(v) is contained in [k] (arbitrary)v ∈ V, find a labeling l(v) ∈ 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 Δ_(k,q) = {x ∈ R_+~k : Σ_(i=1)~k x_i = q} such that for any division of q units of a resource, (x_, x_2,..., x_k) ∈ Δ_(k,q) such that Σ_(i=1)~k 「x_i」 = 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.
展开▼
