Existence of balanced simplices on polytopes. (English) Zbl 1091.52007
Summary: The classic Sperner lemma states that in a simplicial subdivision of a simplex in \(\mathbb R^n\) and a labelling rule satisfying some boundary condition there is a completely labeled simplex. In this paper we first generalize the concept of completely labeled simplex to the concept of a balanced simplex. Using this latter concept we then present a general combinatorial theorem, saying that under rather mild boundary conditions on a given labelling function there exists a balanced simplex for any given simplicial subdivision of a polytope. This theorem implies the well-known lemmas of Sperner, Scarf, Shapley, and Garcia as well as some other results as special cases. An even more general result is obtained when the boundary conditions on the labelling function are not required to hold. This latter result includes several results of Freund and Yamamoto as special cases.
MSC:
| 52B11 | \(n\)-dimensional polytopes |
References:
| [1] | Bapat, R. B., A constructive proof of a permutation-based generalization of Sperner’s lemma, Math. Programming, 44, 113-120 (1989) · Zbl 0673.55004 |
| [2] | Cohen, D. I.A., On the Sperner lemma, J. Combin. Theory, 2, 585-587 (1967) · Zbl 0163.18104 |
| [3] | Doup, T. M., Simplicial Algorithms on the Simplotope. Simplicial Algorithms on the Simplotope, Lecture Notes in Economics and Mathematical Systems, 318 (1988), Springer-Verlag: Springer-Verlag Berlin · Zbl 0697.90046 |
| [4] | Eaves, B. C., Homotopies for computation of fixed points, Math. Programming, 31, 1-22 (1972) · Zbl 0276.55004 |
| [5] | Fan, K., Simplicial maps from an orientable \(n\)-pseudomanifold into \(S^m\) with the octahedral triangulation, J. Combin. Theory, 2, 588-602 (1967) · Zbl 0149.41302 |
| [6] | Forster, W., Numerical Solution of Highly Nonlinear Problems (1980), North-Holland: North-Holland Amsterdam · Zbl 0416.00020 |
| [7] | Freund, R. W., Variable dimension complexes Part II: A unified approach to some combinatorial lemmas in topology, Math. Oper. Res., 9, 498-509 (1984) · Zbl 0556.57015 |
| [8] | Freund, R. W., Combinatorial theorems on the simplotope that generalize results on the simplex and cube, Math. Oper. Res., 11, 169-179 (1986) · Zbl 0598.05024 |
| [9] | Freund, R. W., Combinatorial analogs of Brouwer’s fixed point theorem on a bounded polyhedron, J. Combin. Theory Ser. B, 2, 192-219 (1989) · Zbl 0723.55001 |
| [10] | Garcia, C. B., A hybrid algorithm for the computation of fixed points, Manag. Sci., 22, 606-613 (1976) · Zbl 0358.90032 |
| [11] | Grunbaum, B., Convex Polytopes (1967), Wiley: Wiley London · Zbl 0163.16603 |
| [12] | Kuhn, H. W., Simplicial approximation of fixed points, Proc. Nat. Acad. of Sci., 61, 1238-1242 (1968) · Zbl 0191.54904 |
| [13] | van der Laan, G.; Talman, A. J.J., A restart algorithm for computing fixed points without an extra dimension, Math. Programming, 17, 74-84 (1979) · Zbl 0411.90061 |
| [14] | van der Laan, G.; Talman, A. J.J., Labeling rules and orientation: Sperner’s lemma and Brouwer’s degree, (Allgower, E. L.; Glashoff, K.; Peitgen, H. O., Numerical Solution of Nonlinear Equations. Numerical Solution of Nonlinear Equations, Lecture Notes in Mathematics, 878 (1981), Springer-Verlag: Springer-Verlag Berlin), 238-257 · Zbl 0461.65039 |
| [15] | van der Laan, G.; Talman, A. J.J., On the computation of fixed points in the product space of unit simplices and an application to noncooperative N-person game, Math. Oper. Res., 7, 1-13 (1982) · Zbl 0497.90063 |
| [16] | van der Laan, G.; Talman, A. J.J.; Van der Heyden, L., Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product space of unit simplices using a general labeling rule, Math. of Oper. Res., 12, 377-397 (1987) · Zbl 0638.90096 |
| [17] | Le Van, C., Topological degree and Sperner’s lemma, J. Optim. Theory Appl., 37, 371-377 (1982) · Zbl 0466.55001 |
| [18] | Merill, O. H., Applications and Extensions of an Algorithm That Compute Fixed Points of Certain Upper Semi-Continuous Point to Set Mappings (1972), University of MichiganDepartment of Industrial and Operations Engineering: University of MichiganDepartment of Industrial and Operations Engineering Ann Arbor |
| [19] | Scarf, H., The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15, 1328-1343 (1967) · Zbl 0153.49401 |
| [20] | Scarf, H., The Computation of Economic Equilibria (1973), Yale Univ. Press: Yale Univ. Press New Haven · Zbl 0311.90009 |
| [21] | Shapley, L. S., On balanced games without side payments, (Hu, T. C.; Robinson, S. M., Mathematical Programming (1973), Academic Press: Academic Press New York), 261-290 · Zbl 0267.90100 |
| [22] | Sperner, E., Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes, Abh. Math. Sem. Univ. Hamburg, 6, 265-272 (1928) · JFM 54.0614.01 |
| [23] | Todd, M. J., The Computation of Fixed Points and Applications. The Computation of Fixed Points and Applications, Lecture Notes in Economics and Mathematical Systems, 124 (1976), Springer-Verlag: Springer-Verlag Berlin · Zbl 0332.54003 |
| [24] | Tucker, A. W., Some topological properties of disk and sphere, Proceedings of the first Canadian Mathematical Congress (1946), Univ. of Toronto Press: Univ. of Toronto Press Toronto, p. 285-309 · Zbl 0061.40305 |
| [25] | Yamamoto, Y., Orientability of a pseudomanifold and generalization of Sperner’s lemma, J. Oper. Res. Soc. Japan, 31, 19-42 (1988) · Zbl 0655.90071 |
| [26] | Yang, Z., Computing Equilibria and Fixed Points (1999), Kluwer Academic: Kluwer Academic Boston · Zbl 0947.91060 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
