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.
The KKM requirements are satisfied, since: 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.
Additionally, each result in the top row can be deduced from the one below it in the same column.
[2] David Gale proved the following generalization of the KKM lemma.
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".
[4] The original KKM lemma follows from the rainbow KKM lemma by simply picking n identical coverings.
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 KKMS theorem is a generalization of the KKM lemma by Lloyd Shapley.
closed sets - indexed by the nonempty subsets of
should be covered by the union of sets corresponding to subsets of
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.
is nonempty:[7] It remains to explain what a "balanced collection" is.
is called balanced if there is a weight function on
, the sum of weights of all subsets containing
Then: 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.
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.
[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] Hidetoshi Komiya generalized the KKMS theorem from simplices to polytopes.
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
, 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.
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.
