Existence of balanced simplices on polytopes

The classic Sperner lemma states that in a simplicial subdivision of a simp lex in R-n and a labelling rule satisfying some boundary condition there is a completely labeled simplex. In this paper we First generalize the concep t of completely labeled simplex to the concept of a balanced simplex. Using this latter concept we then present a general combinatorial theorem, sayin g that under rather mild boundary conditions on a given labelling function there exists it balanced simplex for,my given simplicial subdivision of a p olytope, This theorem implies the well-known lemmas of Sperner, Scarf, Shap ley, and Garcia as well as some other results as special cases. An even mor e general result is obtained when the boundary conditions oil the labelling function are not required to hold. This latter result includes several res ults of Freund and Yamamoto as special cases. (C) 2001 Academic Press.