![]() | ||
The Knaster–Kuratowski–Mazurkiewicz lemma is a basic result in mathematical fixed-point theory published in 1929 by Knaster, Kuratowski and Mazurkiewicz.
Contents
- Statement
- Example
- Equivalent results
- Permutations
- Connecting sets
- The KKMS theorem
- Boundary conditions
- References
The KKM lemma can be proved from Sperner's lemma and can be used to prove the Brouwer fixed-point theorem.
Statement
Let
A KKM covering is defined as a set
The KKM lemma says that a KKM covering has a non-empty intersection, i.e:
Example
The case
The KKM lemma states that the sets
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:
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.
Permutations
David Gale proved the following generalization of the KKM lemma. Suppose that, instead of one KKM covering, we have n different KKM coverings:
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".
Ravindra Bapat provided an alternative proof of this generalization, based on the permutation variant of Sperner's lemma.
Note: the original KKM lemma follows from the permutation lemma by simply picking n identical coverings.
Connecting-sets
A connecting set of a simplex is a connected set that touches all n faces of the simplex.
A generalized KKM covering is a covering
Any KKM-covering is a generalized-KKM-covering, since in a KKM covering, no
A theorem of Ravindra Bapat, generalizing Sperner's lemma, implies 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.
While a KKM covering contains n sets, a KKMS covering contains
The KKMS theorem says that for any KKMS covering, there is a balanced collection
It remains to explain what a "balanced collection" is. A collection
The KKMS theorem implies the KKM lemma. Suppose we have a KKM covering
The KKM condition on the original covering
The KKMS theorem has various proofs.
Reny and Holtz proved that the balanced set can also be chosen to be partnered.
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.