THE SIMPLEX REMINISCENT OF SPERNER’S LEMMA

Abstract: We prove three results about colorings of the simplex reminiscent of Sperner's Lemma in hardness of approximation and fair division. First, let and Then for every Sperner-admissible labeling (l : Vk,q ? [k] such that vl(v) > 0 for each v ? Vk,q), there are at least 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 in a k-uniform hypergraph H = (V, E) with color lists L(v) ? [k] ?v ? V. To prove 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 Vk,q such that every hyperedge 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 = such that for any division of q units of a resource, (x1, x2, . . . ., xk) ? ?k,q such that at most 4 players out of k are satisfied.

Keywords: Sperner's Lemma, hyper graph label and hyper graph label and hyper graph colouring. MSC Code : 05C65,05C90.