zbMATH — the first resource for mathematics

A constructive proof of a permutation-based generalization of Sperner’s lemma. (English) Zbl 0673.55004
Summary: In a recent paper, D. Gale [Int. J. Game Theory 13, 61-64 (1984; Zbl 0531.90011)] has given an interesting generalization of the KKM lemma in combinatorial topology. We present a similar generalization of Sperner’s well-known lemma and give a constructive proof. The argument uses the familiar idea of following simplicial paths in a triangulation. To demonstrate that the algorithm must work, orientation considerations are necessary. Gale’s generalized KKM lemma is derived from the main result. A permutation-based generalization of Brouwer’s fixed point theorem is also given.

55M99 Classical topics in algebraic topology
57Q99 PL-topology
55M20 Fixed points and coincidences in algebraic topology
55M10 Dimension theory in algebraic topology
05B99 Designs and configurations
05C99 Graph theory
Full Text: DOI
[1] D.I.A. Cohen, ”On the Sperner lemma,”Journal of Combinatorial Theory 2 (1967) 585–587. · Zbl 0163.18104
[2] B.C. Eaves, ”Properly labelled simplices,” in: G.B. Dantzig and B.C. Eaves, eds.,Studies in Optimization, MAA Studies in Mathematics, Volume 10 (The Mathematical Association of America, 1974) pp. 71–93.
[3] K. Fan, ”Simplicial maps from an orientablen-pseudomanifold intoS m with the octahedral triangulation,”Journal of Combinatorial Theory 2 (1967) 588–602. · Zbl 0149.41302
[4] R.M. Freund, ”Variable dimension complexes, Part II. A unified approach to some combinatorial lemmas in topology,”Mathematics of Operations Research 9 (1984) 498–509. · Zbl 0556.57015
[5] R.M. Freund, ”Combinatorial theorems on the simplotope that generalizes results on the simplex and cube,”Mathematics of Operations Research 11 (1986) 169–179. · Zbl 0598.05024
[6] D. Gale, ”Equilibrium in a discrete exchange economy with money,”International Journal of Game Theory 13 (1984) 61–64. · Zbl 0531.90011
[7] C.E. Lemke and S.J. Grotzinger, ”On generalizing Shapley’s index theory to labelled pseudomani-folds,”Mathematical Programming 10 (1976) 245–262. · Zbl 0345.90058
[8] C.E. Lemke and J.I. Howson, ”Equilibrium points of bimatrix games,”SIAM Journal on Applied Mathematics 12 (1964) 413–423. · Zbl 0128.14804
[9] H. Scarf, ”The approximation of fixed points of a continuous mapping,”SIAM Journal on Applied Mathematics 15 (1967) 1328–1343. · Zbl 0153.49401
[10] H. Scarf, with the collaboration of T. Hansen,Computation of Economic Equilibria (Yale University Press, New Haven, 1973). · Zbl 0311.90009
[11] M.J. Todd,The Computation of Fixed Points and Applications (Springer, Berlin, 1976). · Zbl 0332.54003
[12] M.J. Todd, ”Orientation in complementary pivot algorithms,”Mathematics of Operations Research 1 (1976) 54–66. · Zbl 0457.90074
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.