Multilabeled Versions of Sperner's and Fan's Lemmas and Applications

DOI10.1137/18M1192548zbMATH Open1427.55002arXiv1801.02044WikidataQ124846300 ScholiaQ124846300MaRDI QIDQ5234532FDOQ5234532

Authors: Frédéric Meunier, Francis Edward Su 

Publication date: 27 September 2019

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1801.02044

Recommendations

• scientific article; zbMATH DE number 5639861
• On Vizing's theorem, adjacency lemma and fan argument generalized to multigraphs
• scientific article; zbMATH DE number 4066896
• scientific article; zbMATH DE number 4111577
• Generalizations of Tucker-Fan-Shashkin lemmas
• A polytopal generalization of Sperner's lemma
• A generalization of Fiedler's lemma and some applications
• A New Version of the Multivalued Fatou Lemma
• Multiplicity one theorems, \(S\)-version
• Farkas' lemma and multilinear forms

zbMATH Keywords

graph coloringSperner's lemmacake-cuttinglabelingsFan's lemmaconsensus-halving

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Combinatorial aspects of simplicial complexes (05E45) Fixed-point and coincidence theorems (topological aspects) (54H25) Fixed points and coincidences in algebraic topology (55M20)

Cites Work

• Kneser's conjecture, chromatic number, and homotopy
• Rental Harmony: Sperner's Lemma in Fair Division
• Local chromatic number, Ky Fan's theorem, and circular colorings
• A Borsuk-Ulam equivalent that directly implies Sperner's lemma
• A constructive proof of Ky Fan's generalization of Tucker's lemma
• A generalization of Tucker's combinatorial lemma with topological applications
• A polytopal generalization of Sperner's lemma
• Equivalent Formulations of the Borsuk-Ulam Theorem
• A Moment Problem in L 1 Approximation
• Splitting necklaces
• Splitting multidimensional necklaces
• Equilibrium in a discrete exchange economy with money
• How to Cut a Cake Fairly
• Dividing a cake fairly
• Colourful theorems and indices of homomorphism complexes
• Title not available (Why is that?)
• Strengthening topological colorful results for graphs
• Colorful subhypergraphs in uniform hypergraphs
• Bisection of Circle Colorings
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• A constructive proof of a permutation-based generalization of Sperner's lemma
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Necklace bisection with one cut less than needed
• STRENGTHENING OF SPERNER'S LEMMA APPLIED TO HOMOLOGY THEORY
• A counting lemma and multiple combinatorial Stokes' theorem
• Combinatorial necklace splitting
• Oriented matroids and Ky Fan's theorem
• Fair division and generalizations of Sperner- and KKM-type results
• Achieving rental harmony with a secretive roommate

Cited In (16)

• Title not available (Why is that?)
• Envy-free division in the presence of a dragon
• Discrete geometry. Abstracts from the workshop held September 20--26, 2020 (hybrid meeting)
• Fair division and generalizations of Sperner- and KKM-type results
• Sperner labellings: A combinatorial approach
• Generalized rental harmony
• Title not available (Why is that?)
• Envy-free division of multi-layered cakes
• Sperner's colorings and optimal partitioning of the simplex
• How to cut a cake fairly: a generalization to groups
• A Borsuk-Ulam equivalent that directly implies Sperner's lemma
• A sparse colorful polytopal KKM theorem
• Rental Harmony: Sperner's Lemma in Fair Division
• Fair distributions for more participants than allocations
• Title not available (Why is that?)
• A tree Sperner lemma

This page was built for publication: Multilabeled Versions of Sperner's and Fan's Lemmas and Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5234532)