A Polytopal Generalization of Sperner's Lemma

✍ Scribed by Jesus A. De Loera; Elisha Peterson; Francis Edward Su

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 235 KB
• Volume: 100
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.2002.3274

✦ Synopsis

We prove the following conjecture of Atanassov (Studia Sci. Math. Hungar. 32 (1996), 71-74). Let T be a triangulation of a d-dimensional polytope P with n vertices v 1 ; v 2 ; . . . ; v n : Label the vertices of T by 1; 2; . . . ; n in such a way that a vertex of T belonging to the interior of a face F of P can only be labelled by j if v j is on F: Then there are at least n À d full dimensional simplices of T; each labelled with d þ 1 different labels. We provide two proofs of this result: a non-constructive proof introducing the notion of a pebble set of a polytope, and a constructive proof using a path-following argument. Our non-constructive proof has interesting relations to minimal simplicial covers of convex polyhedra and their chamber complexes, as in