Everipedia Logo
Everipedia is now IQ.wiki - Join the IQ Brainlist and our Discord for early access to editing on the new platform and to participate in the beta testing.
Knaster–Kuratowski–Mazurkiewicz lemma

Knaster–Kuratowski–Mazurkiewicz lemma

The Knaster–Kuratowski–Mazurkiewicz lemma is a basic result in mathematical fixed-point theory published in 1929 by Knaster, Kuratowski and Mazurkiewicz.[1]

The KKM lemma can be proved from Sperner's lemma and can be used to prove the Brouwer fixed-point theorem.

Statement

Letbe a-dimensionalsimplexwith nverticeslabeled as.
A KKM covering is defined as a setofclosed setssuch that for any, theconvex hullof the vertices corresponding toiscoveredby.

The KKM lemma says that a KKM covering has a non-empty intersection, i.e:

.

Example

The casemay serve as an illustration. In this case the simplexis a triangle, whose vertices we can label 1, 2 and 3. We are given three closed setssuch that:
  • covers vertex 1, covers vertex 2, covers vertex 3.

  • The edge 12 (from vertex 1 to vertex 2) is covered by the sets and , the edge 23 is covered by the sets and , the edge 31 is covered by the sets and .

  • The union of all three sets covers the entire triangle

The KKM lemma states that the setshave at least one point in common.

The lemma is illustrated by the picture on the right, in which set #1 is blue, set #2 is red and set #3 is green. The KKM requirements are satisfied, since:

  • Each vertex is covered by a unique color.

  • Each edge is covered by the two colors of its two vertices.

  • The triangle is covered by all three colors.

The KKM lemma states that there is a point covered by all three colors simultaneously; such a point is clearly visible in the picture.

Equivalent results

There are several fixed-point theorems which come in three equivalent variants: an algebraic topology variant, a combinatorial variant and a set-covering variant. Each variant can be proved separately using totally different arguments, but each variant can also be reduced to the other variants in its row. Additionally, each result in the top row can be deduced from the one below it in the same column.[2]

Algebraic topologyCombinatoricsSet covering
Brouwer fixed-point theoremSperner's lemmaKnaster–Kuratowski–Mazurkiewicz lemma
Borsuk–Ulam theoremTucker's lemmaLusternik–Schnirelmann theorem

Generalizations

Permutations

David Galeproved the following generalization of the KKM lemma.[3] Suppose that, instead of one KKM covering, we have n different KKM coverings:. Then, there exists a permutationof the coverings with a non-empty intersection, i.e:
.

Gale wrote about his lemma: "A colloquial statement of this result is the red, white and blue lemma which asserts that if each of three people paint a triangle red, white and blue according to the KKM rules, then there will be a point which is in the red set of one person, the white set of another, the blue of the third".[3]

Ravindra Bapat provided an alternative proof of this generalization, based on the permutation variant of Sperner's lemma.[4]

Note: the original KKM lemma follows from the permutation lemma by simply picking n identical coverings.

Connecting-sets

Image

A connecting set of a simplex is a connected set that touches all n faces of the simplex.

A generalized KKM covering is a coveringin which nocontains a connecting set.
Any KKM-covering is a generalized-KKM-covering, since in a KKM covering, noeven touches all n faces. However, there are generalized-KKM-coverings that are not KKM-coverings. An example is illustrated at the right. There, the red set touches all three faces, but it does not contain any connecting-set, since no connected component of it touches all three faces.
A theorem ofRavindra Bapat, generalizingSperner's lemma,[5]:chapter 16, pp. 257-261implies that the KKM lemma is true for generalized KKM coverings (he proved his theorem for).

The connecting-set variant also has a permutation variant, so that both these generalizations can be used simultaneously.

The KKMS theorem

The KKMS theorem is a generalization of the KKM lemma by Lloyd Shapley. It is useful in economics, especially in cooperative game theory.[6]

While a KKM covering contains n sets, a KKMS covering containssets - indexed by the nonempty subsets of. For any, theconvex hullof the vertices corresponding toshould becoveredby.
The KKMS theorem says that for any KKMS covering, there is a balanced collection, such that the intersection of sets indexed byis nonempty:[7]
It remains to explain what a "balanced collection" is. A collectionof subsets ofis called balanced if, for each subset, we can select a weight, such that, for each element, the sum of weights of all subsets that containis exactly 1. For example, suppose. Then:
  • The collection {{1}, {2}, {3}} is balanced: choose all weights to be 1. The same is true for any collection in which each element appears exactly once, such as the collection {{1,2},{3}} or the collection { {1,2,3} }.

  • The collection {{1,2}, {2,3}, {3,1}} is balanced: choose all weights to be 1/2. The same is true for any collection in which each element appears exactly twice.

  • The collection {{1,2}, {2,3}} is not balanced, since for any choice of positive weights, the sum for element 2 will be larger than the sum for element 1 or 3, so it is not possible that all sums equal 1.

  • The collection {{1,2}, {2,3}, {1}} is balanced: choose .

The KKMS theorem implies the KKM lemma.[7] Suppose we have a KKM covering, for. Construct a KKMS coveringas follows:
  • whenever ( is a singleton that contains only element ).

  • otherwise.

The KKM condition on the original coveringimplies the KKMS condition on the new covering. Therefore, there exists a balanced collection such that the corresponding sets in the new covering have nonempty intersection. But the only possible balanced collection is the collection of all singletons; hence, the original covering has nonempty intersection.

The KKMS theorem has various proofs.[8][9][10]

Reny and Wooders proved that the balanced set can also be chosen to be partnered.[11]

Boundary conditions

Oleg R. Musin proved several generalizations of the KKM lemma and KKMS theorem, with boundary conditions on the coverings. The boundary conditions are related to homotopy.[12][13]

References

[1]
Citation Linkeudml.orgKnaster, B.; Kuratowski, C.; Mazurkiewicz, S. (1929), "Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe", Fundamenta Mathematicae (in German), 14 (1): 132–137.
Sep 21, 2019, 2:37 AM
[2]
Citation Link//www.ams.org/mathscinet-getitem?mr=3035127Nyman, Kathryn L.; Su, Francis Edward (2013), "A Borsuk–Ulam equivalent that directly implies Sperner's lemma", American Mathematical Monthly, 120 (4): 346–354, doi:10.4169/amer.math.monthly.120.04.346, MR 3035127
Sep 21, 2019, 2:37 AM
[3]
Citation Link//doi.org/10.1007%2FBF01769865Gale, D. (1984). "Equilibrium in a discrete exchange economy with money". International Journal of Game Theory. 13: 61. doi:10.1007/BF01769865.
Sep 21, 2019, 2:37 AM
[4]
Citation Link//doi.org/10.1007%2FBF01587081Bapat, R. B. (1989). "A constructive proof of a permutation-based generalization of Sperner's lemma". Mathematical Programming. 44: 113. doi:10.1007/BF01587081.
Sep 21, 2019, 2:37 AM
[5]
Citation Linkbooks.google.comBapat, Ravindra (2009-04-03). Modeling, Computation and Optimization. World Scientific. ISBN 9789814467896.
Sep 21, 2019, 2:37 AM
[6]
Citation Link//doi.org/10.1007%2FBF01210576Shapley, Lloyd; Vohra, Rajiv (1991). "On Kakutani's fixed point theorem, the K-K-M-S theorem and the core of a balanced game". Economic Theory. 1: 108. doi:10.1007/BF01210576.
Sep 21, 2019, 2:37 AM
[7]
Citation Link//doi.org/10.1016%2F0022-247X%2881%2990063-9Ichiishi, Tatsuro (1981). "On the Knaster-Kuratowski-Mazurkiewicz-Shapley theorem". Journal of Mathematical Analysis and Applications. 81 (2): 297. doi:10.1016/0022-247X(81)90063-9.
Sep 21, 2019, 2:37 AM
[8]
Citation Link//doi.org/10.1007%2FBF01215384Krasa, Stefan; Yannelis, Nicholas C. (1994). "An elementary proof of the Knaster-Kuratowski-Mazurkiewicz-Shapley Theorem". Economic Theory. 4 (3): 467. doi:10.1007/BF01215384.
Sep 21, 2019, 2:37 AM
[9]
Citation Link//doi.org/10.1007%2FBF01215383Komiya, Hidetoshi (1994). "A simple proof of K-K-M-S theorem". Economic Theory. 4 (3): 463. doi:10.1007/BF01215383.
Sep 21, 2019, 2:37 AM
[10]
Citation Link//doi.org/10.1007%2Fs001990050161Herings, P. Jean-Jacques (1997). "An extremely simple proof of the K-K-M-S Theorem". Economic Theory. 10 (2): 361. doi:10.1007/s001990050161.
Sep 21, 2019, 2:37 AM
[11]
Citation Link//doi.org/10.1016%2FS0304-4068%2897%2900004-9Reny, Philip J.; Holtz Wooders, Myrna (1998). "An extension of the KKMS theorem". Journal of Mathematical Economics. 29 (2): 125. doi:10.1016/S0304-4068(97)00004-9.
Sep 21, 2019, 2:37 AM
[12]
Citation Link//arxiv.org/archive/math.ATMusin, Oleg R. (2015). "KKM type theorems with boundary conditions". arXiv:1512.04612 [math.AT].
Sep 21, 2019, 2:37 AM
[13]
Citation Link//doi.org/10.2140%2Fagt.2016.16.1799Musin, Oleg R. (2015). "Homotopy invariants of covers and KKM type lemmas". Algebraic & Geometric Topology. 16 (3): 1799–1812. arXiv:1505.07629. doi:10.2140/agt.2016.16.1799.
Sep 21, 2019, 2:37 AM
[14]
Citation Linkplanetmath.orgPlanet Math
Sep 21, 2019, 2:37 AM
[15]
Citation Linkeudml.org"Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe"
Sep 21, 2019, 2:37 AM
[16]
Citation Linkdoi.org10.4169/amer.math.monthly.120.04.346
Sep 21, 2019, 2:37 AM
[17]
Citation Linkwww.ams.org3035127
Sep 21, 2019, 2:37 AM
[18]
Citation Linkdoi.org10.1007/BF01769865
Sep 21, 2019, 2:37 AM
[19]
Citation Linkdoi.org10.1007/BF01587081
Sep 21, 2019, 2:37 AM
[20]
Citation Linkbooks.google.comModeling, Computation and Optimization
Sep 21, 2019, 2:37 AM