DMGT

Discussiones Mathematicae Graph Theory 26(3) (2006) 439-338
DOI: https://doi.org/10.7151/dmgt.1336

COMBINATORIAL LEMMAS FOR POLYHEDRONS I

Adam Idzik

Akademia Świetokrzyska
Świetokrzyska 15, 25-406 Kielce, Poland
and
Institute of Computer Science, Polish Academy of Sciences
Ordona 21, 01-237 Warsaw, Poland
e-mail: adidzik@ipipan.waw.pl

Konstanty Junosza-Szaniawski

Warsaw University of Technology
Pl. Politechniki 1, 00-661 Warsaw, Poland
e-mail: k.szaniawski@mini.pw.edu.pl

Abstract

We formulate general boundary conditions for a labelling of vertices of a triangulation of a polyhedron by vectors to assure the existence of a balanced simplex. The condition is not for each vertex separately, but for a set of vertices of each boundary simplex. This allows us to formulate a theorem, which is more general than the Sperner lemma and theorems of Shapley; Idzik and Junosza-Szaniawski; van der Laan, Talman and Yang. A generalization of the Poincaré-Miranda theorem is also derived.

Keywords: b-balanced simplex, labelling, polyhedron, simplicial complex, Sperner lemma.

2000 Mathematics Subject Classification: 05B30, 47H10, 52A20, 54H25.

References

[1]	A.D. Alexandrov, Convex Polyhedra (Springer, Berlin, 2005).
[2]	R.W. Freund, Variable dimension complexes Part II: A unified approach to some combinatorial lemmas in topology, Math. Oper. Res. 9 (1984) 498-509, doi: 10.1287/moor.9.4.498.
[3]	C.B. Garcia, A hybrid algorithm for the computation of fixed points, Manag. Sci. 22 (1976) 606-613, doi: 10.1287/mnsc.22.5.606.
[4]	B. Grunbaum, Convex Polytopes (Wiley, London, 1967).
[5]	A. Idzik and K. Junosza-Szaniawski, Combinatorial lemmas for nonoriented pseudomanifolds, Top. Meth. in Nonlin. Anal. 22 (2003) 387-398.
[6]	A. Idzik and K. Junosza-Szaniawski, Combinatorial lemmas for polyhedrons, Discuss. Math. Graph Theory 25 (2005) 95-102, doi: 10.7151/dmgt.1264.
[7]	B. Knaster, C. Kuratowski and S. Mazurkiewicz, Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe, Fund. Math. 14 (1929) 132-137.
[8]	W. Kulpa, Poincaré and Domain Invariance Theorem, Acta Univ. Carolinae - Mathematica et Physica 39 (1998) 127-136.
[9]	G. van der Laan, D. Talman and Z. Yang, Existence of balanced simplices on polytopes, J. Combin. Theory (A) 96 (2001) 25-38, doi: 10.1006/jcta.2001.3178.
[10]	H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math. 15 (1967) 1328-1343, doi: 10.1137/0115116.
[11]	L.S. Shapley, On balanced games without side payments, in: T.C. Hu and S.M. Robinson (eds.), Mathematical Programming, New York: Academic Press (1973) 261-290.
[12]	E. Sperner, Neuer Beweis für die Invarianz der Dimensionszahl und des Gebiets, Abh. Math. Sem. Univ. Hamburg 6 (1928) 265-272, doi: 10.1007/BF02940617.

Received 2 December 2005
Revised 3 October 2006