A tree Sperner lemma

MaRDI QIDQ3464533zbMATH OpenFDO

Authors Andrew Niedermaier, Douglas Rizzolo, Francis Edward Su

Publication date 27 January 2016

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

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)

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.

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

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)