Multilabeled versions of Sperner's and Fan's lemmas and applications

2018/01/06 by Meunier, Frédéric, Su, Francis Edward · 2 citations
#05E45 #91B32 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Primary 55M20 #Secondary 54H25

paper · doi:10.48550/arxiv.1801.02044

Abstract

We propose a general technique related to the polytopal Sperner lemma for proving old and new multilabeled versions of Sperner's lemma. A notable application of this technique yields a cake-cutting theorem where the number of players and the number of pieces can be independently chosen. We also prove multilabeled versions of Fan's lemma, a combinatorial analogue of the Borsuk-Ulam theorem, and exhibit applications to fair division and graph coloring.

Cited by

• Fair Allocation of Indivisible Goods with Variable Groups
• Covering and labeling generalizations of the Borsuk-Ulam theorem

Related

• A Geometric Approach to Combinatorial Fixed-Point Theorems
• Homotopies and transcendental extensions in colouring problems
• Criticality in Sperner's Lemma
• A Tree Sperner Lemma
• Meunier Conjecture