Discussiones Mathematicae Graph Theory 25(1-2) (2005) 95-102

COMBINATORIAL LEMMAS FOR POLYHEDRONS

Adam Idzik

Akademia Œwietokrzyska
15 Œwietokrzyska street, 25-406 Kielce, Poland
and
Institute of Computer Science
Polish Academy of Sciences
21 Ordona street, 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 to assure the existence of a balanced n-simplex in a triangulated polyhedron. Furthermore we prove a Knaster-Kuratowski-Mazurkiewicz type theorem for polyhedrons and generalize some theorems of Ichiishi and Idzik. We also formulate a necessary condition for a continuous function defined on a polyhedron to be an onto function.

Keywords: KKM covering, labelling, primoid, pseudomanifold, simplicial complex, Sperner lemma.

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

References

[1]

T. Ichiishi and A. Idzik, Closed coverings of convex polyhedra, Internat. J. Game Theory 20 (1991) 161-169.

[2]

T. Ichiishi and A. Idzik, Equitable allocation of divisible goods, J. Math. Econom. 32 (1998) 389-400.

[3]

A. Idzik and K. Junosza-Szaniawski, Combinatorial lemmas for nonoriented pseudomanifolds, Top. Meth. in Nonlin. Anal. 22 (2003) 387-398.

[4]

B. Knaster, C. Kuratowski and S. Mazurkiewicz, Ein beweis des fixpunktsatzes für n-dimensionale simplexe, Fund. Math. 14 (1929) 132-137.

[5]

W. Kulpa, Poincaré and domain invariance theorem, Acta Univ. Carolinae - Mathematica et Physica 39 (1998) 127-136.

[6]

G. van der Laan, D. Talman and Z. Yang, Intersection theorems on polytypes, Math. Programming 84 (1999) 333-352.

[7]

G. van der Laan, D. Talman and Z. Yang, Existence of balanced simplices on polytopes, J. Combin. Theory (A) 96 (2001) 25-38.

[8]

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.

[9]

E. Sperner, Neuer beweis für die invarianz der dimensionszahl und des gebiets, Abh. Math. Sem. Univ. Hamburg 6 (1928) 265-272.

Recived 3 November 2003
Revised 21 March 2005