A tree Sperner lemma

zbMATH Open1331.05186arXiv0909.0339MaRDI QIDQ3464533FDOQ3464533

Authors: Andrew Niedermaier, Douglas Rizzolo, Francis Edward Su 

Publication date: 27 January 2016

Abstract: In this paper we prove a combinatorial theorem for finite labellings of trees, and show that it is equivalent to a theorem for finite covers of metric trees and a fixed point theorem on metric trees. We trace how these connections mimic the equivalence of the Brouwer fixed point theorem with the classical KKM lemma and Sperner's lemma. We also draw connections to a KKM-type theorem about infinite covers of metric trees and fixed point theorems for non-compact metric trees. Finally, we develop a new KKM-type theorem for cycles, and discuss interesting social consequences, including an application in voting theory.

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

Recommendations

• An aspect of Sperner's lemma as a fixed point theorem
• A Borsuk-Ulam equivalent that directly implies Sperner's lemma
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
• A direct proof of Shapley-Sperner's lemma based on the KKMS lemma
• A proof of the Sperner lemma from the Brouwer fixed point theorem

zbMATH Keywords

KKM lemmafinite labellings of trees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Fixed points and coincidences in algebraic topology (55M20)

Cited In (1)

• Piercing numbers in approval voting

This page was built for publication: A tree Sperner lemma

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