A polytopal generalization of Sperner's lemma (Q1865380): Difference between revisions

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.