A polytopal generalization of Sperner's lemma

[摘要] 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 Alekseyevskaya (Discrete Math. 157 (1996), 15-37) and Billera et al. (J. Combin. Theory Ser. B 57 (1993), 258-268). (C) 2002 Elsevier Scietice (USA).

[发布日期] 2002-10-01

[关键词] Sperner's lemma;polytopes;path-following;simplicial algorithms