A Polytopal Generalization of Sperner's Lemma

Authors

Jesus A. De Loera, University of California - Davis
Elisha Peterson '00, Harvey Mudd CollegeFollow
Francis E. Su, Harvey Mudd CollegeFollow

Student Co-author

HMC Undergraduate

Document Type

Article - preprint

Department

Mathematics (HMC)

Publication Date

10-2002

Abstract

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₁, v₂,…,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 Alekseyevskaya (Discrete Math.157 (1996), 15–37) and Billera et al. (J. Combin. Theory Ser. B57 (1993), 258–268).

Comments

Author's pre-print manuscript available for download.

For the publisher's version, please visit http://dx.doi.org/10.1006/jcta.2002.3274.

Rights Information

© 2002 Elsevier

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1006/jcta.2002.3274

Recommended Citation

Jesus A. De Loera, Elisha Peterson, and Francis Edward Su. A polytopal generalization of Sperner's lemma. J. Combin. Theory Ser. A, 100(1):1–26, 2002.