Knaster–Kuratowski–Mazurkiewicz lemma

(Redirected from KKM 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

edit

Let   be an  -dimensional simplex with n vertices labeled as  .

A KKM covering is defined as a set   of closed sets such that for any  , the convex hull of the vertices corresponding to   is covered by  .

The KKM lemma says that in every KKM covering, the common intersection of all n sets is nonempty, i.e:

 

Example

edit

When  , the KKM lemma considers the simplex   which is a triangle, whose vertices can be labeled 1, 2 and 3. We are given three closed sets   such 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 sets   have at least one point in common.

 
An example of a covering satisfying the requirements of the KKM lemma

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.

Note that it is important that all sets are closed, i.e., contain their boundary. If, for example, the red set is not closed, then it is possible that the central point is contained only in the blue and green sets, and then the intersection of all three sets may be empty.

Equivalent results

edit

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 topology Combinatorics Set covering
Brouwer fixed-point theorem Sperner's lemma Knaster–Kuratowski–Mazurkiewicz lemma
Borsuk–Ulam theorem Tucker's lemma Lusternik–Schnirelmann theorem

Generalizations

edit

Rainbow KKM lemma (Gale)

edit

David Gale proved 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 permutation   of the coverings with a non-empty intersection, i.e:

 .

The name "rainbow KKM lemma" is inspired by Gale's description of his lemma:

"A colloquial statement of this result is... 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]

The rainbow KKM lemma can be proved using a rainbow generalization of Sperner's lemma.[4]

The original KKM lemma follows from the rainbow KKM lemma by simply picking n identical coverings.

Connector-free lemma (Bapat)

edit
 
An illustration of the generalized KKM lemma by Bapat

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

A connector-free covering is a covering   in which no   contains a connector.

Any KKM covering is a connector-free covering, since in a KKM covering, no   even touches all n faces. However, there are connector-free 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 connector, since no connected component of it touches all three faces.

A theorem of Ravindra Bapat, generalizing Sperner's lemma,[5]: chapter 16, pp. 257–261  implies the KKM lemma extends to connector-free coverings (he proved his theorem for  ).

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

KKMS theorem

edit

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 closed sets, a KKMS covering contains   closed sets - indexed by the nonempty subsets of   (equivalently: by nonempty faces of  ). For any  , the convex hull of the vertices corresponding to   should be covered by the union of sets corresponding to subsets of   , that is:

 .

Any KKM covering is a special case of a KKMS covering. In a KKM covering, the n sets corresponding to singletons are nonempty, while the other sets are empty. However, there are many other KKMS coverings.

in general, it is not true that the common intersection of all   sets in a KKMS covering is nonempty; this is illustrated by the special case of a KKM covering, in which most sets are empty.

The KKMS theorem says that, in every KKMS covering, there is a balanced collection   of  , such that the intersection of sets indexed by   is nonempty:[7]

 

It remains to explain what a "balanced collection" is. A collection   of subsets of   is called balanced if there is a weight function on   (assigning a weight   to every  ), such that, for each element  , the sum of weights of all subsets containing   is 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  .

In hypergraph terminology, a collection B is balanced with respect to its ground-set V, iff the hypergraph with vertex-set V and edge-set B admits a perfect fractional matching.

The KKMS theorem implies the KKM lemma.[7] Suppose we have a KKM covering  , for  . Construct a KKMS covering   as follows:

  •   whenever   (  is a singleton that contains only element  ).
  •   otherwise.

The KKM condition on the original covering   implies 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]

Zhou proved a variant of the KKMS theorem where the covering consists of open sets rather than closed sets.[12]

Polytopal KKMS theorem (Komiya)

edit

Hidetoshi Komiya generalized the KKMS theorem from simplices to polytopes.[9] Let P be any compact convex polytope. Let   be the set of nonempty faces of P. A Komiya covering of P is a family of closed sets   such that for every face  :   Komiya's theorem says that for every Komiya covering of P, there is a balanced collection  , such that the intersection of sets indexed by   is nonempty:[7]

 

Komiya's theorem also generalizes the definition of a balanced collection: instead of requiring that there is a weight function on   such that the sum of weights near each vertex of P is 1, we start by choosing any set of points  . A collection   is called balanced with respect to   iff  , that is, the point assigned to the entire polygon P is a convex combination of the points assigned to the faces in the collection B.

The KKMS theorem is a special case of Komiya's theorem in which the polytope   and   is the barycenter of the face F (in particular,   is the barycenter of  , which is the point   ).

Boundary conditions (Musin)

edit

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.[13][14]

See also

edit

References

edit
  1. ^ Knaster, B.; Kuratowski, C.; Mazurkiewicz, S. (1929), "Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe", Fundamenta Mathematicae (in German), 14 (1): 132–137, doi:10.4064/fm-14-1-132-137.
  2. ^ Nyman, Kathryn L.; Su, Francis Edward (2013), "A Borsuk–Ulam equivalent that directly implies Sperner's lemma", The American Mathematical Monthly, 120 (4): 346–354, doi:10.4169/amer.math.monthly.120.04.346, JSTOR 10.4169/amer.math.monthly.120.04.346, MR 3035127
  3. ^ a b Gale, D. (1984). "Equilibrium in a discrete exchange economy with money". International Journal of Game Theory. 13: 61–64. doi:10.1007/BF01769865. S2CID 154888988.
  4. ^ Bapat, R. B. (1989). "A constructive proof of a permutation-based generalization of Sperner's lemma". Mathematical Programming. 44 (1–3): 113–120. doi:10.1007/BF01587081. S2CID 5325605.
  5. ^ Bapat, Ravindra (2009-04-03). Modeling, Computation and Optimization. World Scientific. ISBN 9789814467896.
  6. ^ Shapley, 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–116. doi:10.1007/BF01210576. S2CID 121027709.
  7. ^ a b c Ichiishi, Tatsuro (1981). "On the Knaster-Kuratowski-Mazurkiewicz-Shapley theorem". Journal of Mathematical Analysis and Applications. 81 (2): 297–299. doi:10.1016/0022-247X(81)90063-9.
  8. ^ Krasa, Stefan; Yannelis, Nicholas C. (1994). "An elementary proof of the Knaster-Kuratowski-Mazurkiewicz-Shapley Theorem". Economic Theory. 4 (3): 467. doi:10.1007/BF01215384. S2CID 15004516.
  9. ^ a b Komiya, Hidetoshi (1994). "A simple proof of K-K-M-S theorem". Economic Theory. 4 (3): 463–466. doi:10.1007/BF01215383. S2CID 123150937.
  10. ^ Herings, P. Jean-Jacques (1997). "An extremely simple proof of the K-K-M-S Theorem". Economic Theory. 10 (2): 361–367. doi:10.1007/s001990050161. S2CID 122754557.
  11. ^ Reny, 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.
  12. ^ Zhou, Lin (1994). "A Theorem on Open Coverings of a Simplex and Scarf's Core Existence Theorem through Brouwer's Fixed Point Theorem". Economic Theory. 4 (3): 473–477. doi:10.1007/BF01215385. ISSN 0938-2259. JSTOR 25054778. S2CID 120862302.
  13. ^ Musin, Oleg R. (2017). "KKM type theorems with boundary conditions". Journal of Fixed Point Theory and Applications. 19 (3): 2037–2049. arXiv:1512.04612. doi:10.1007/s11784-016-0388-7. S2CID 119619991.
  14. ^ Musin, Oleg R. (2016). "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. S2CID 119695004.
  15. ^ Frick, Florian; Zerbib, Shira (2019-06-01). "Colorful Coverings of Polytopes and Piercing Numbers of Colorful d-Intervals". Combinatorica. 39 (3): 627–637. arXiv:1710.07722. doi:10.1007/s00493-018-3891-1. ISSN 1439-6912. S2CID 119176249.
edit