A polytopal generalization of Sperner's lemma
type: Item
instance of: scholarly article
title: A polytopal generalization of Sperner's lemma
zbMATH Open document ID: 1015.05089
author: Elisha Peterson
author: Francis Edward Su
author: Jesús A. De Loera
published in: Journal of Combinatorial Theory. Series A
publication date: 2003-03-26T00:00:00Z
full work available at URL: https://scholarship.claremont.edu/cgi/viewcontent.cgi
review text: Let \(P\) be a \(d\)-polytope with \(n\) (polytope) vertices and a triangulation \(T\), which may have additional (triangulation) vertices both on the boundary or in the interior. Assigning to each triangulation vertex \(v\) of \(T\) a polytope vertex \(p(v)\) of \(P\) yields a Sperner labelling provided that \(p(v)\) is a polytope vertex of the smallest face of \(P\) containing \(v\). In particular, this implies that in a Sperner labelling \(S\) each polytope vertex is mapped to itself. A \(d\)-simplex in \(T\) is called a full cell with respect to \(S\) if all its labels are distinct. The authors prove that for each Sperner labelling of \(T\) there are at least \(n-d\) full cells. Two proofs are given, one constructive, one non-constructive. The non-constructive proof uses the notion of a pebble set: this is a finite set of points in \(P\) such that any \(d\)-simplex spanned by vertices of \(P\) contains at most one point of this set. The authors prove that \(P\) contains a pebble set of size \(n-d\), which can then be used to deduce the aforementioned theorem. Moreover, this yields a generalization which is valid for arbitrary simplicial covers. Sperner's classical lemma says that for each Sperner labelling of a triangulation of a simplex there is an odd number of full cells. The latter is known to be equivalent to Brouwer's theorem on the existence of a fixed point for each continuous map from a disk to itself.
reviewed by: Michael Joswig
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 52B05
zbMATH DE Number: 1888410
zbMATH Keywords: Sperner's lemma
zbMATH Keywords: triangulations of polytopes
zbMATH Keywords: simplicial covers of polytopes
zbMATH Keywords: pebble sets
Wikidata QID: Q56286471
MaRDI profile type: Publication
OpenAlex ID: W2101942472
cites work: Combinatorial bases in systems of simplices and chambers
cites work: Q4892306
cites work: A proof of the lower bound conjecture for convex polytopes
cites work: Duality and minors of secondary polyhedra
cites work: Minimal simplicial dissections and triangulations of convex 3-polytopes
cites work: Extremal properties for dissections of convex 3-polytopes
cites work: On the Sperner lemma
cites work: Combinatorial analogs of Brouwer's fixed-point theorem on a bounded polyhedron
cites work: SIMPLICIAL APPROXIMATION OF FIXED POINTS
cites work: Intersection theorems on polytopes.
cites work: On triangulations of the convex hull of n points
cites work: The Approximation of Fixed Points of a Continuous Mapping
cites work: Consensus-halving via theorems of Borsuk-Ulam and Tucker
cites work: A lower bound for the simplexity of the \(n\)-cube via hyperbolic volumes
cites work: Rental Harmony: Sperner's Lemma in Fair Division
cites work: Extensions of Lemke's algorithm for the linear complementarity problem
cites work: Q4935258
cites work: Lectures on Polytopes
DBLP publication ID: journals/jct/LoeraPS02
DOI: 10.1006/JCTA.2002.3274
description: scientific article; zbMATH DE number 1888410