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 lemma can be proved from Sperner's lemma and can be used to prove the Brouwer fixed-point theorem.

Statement

Let be a -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 a KKM covering has a non-empty intersection, i.e:

Example

The case may serve as an illustration. In this case the simplex is a triangle, whose vertices we can label 1, 2 and 3. We are given three closed sets such that:
The KKM lemma states that the sets have 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:
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

Generalizations

Permutations

proved the following generalization of the KKM lemma.
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:
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 in which no contains a connecting set.
Any KKM-covering is a generalized-KKM-covering, since in a KKM covering, no even 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 of Ravindra Bapat, generalizing Sperner's lemma,
implies that the KKM lemma is true for generalized KKM coverings.
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 closed sets - indexed by the nonempty subsets of. For any, the convex hull of the vertices corresponding to should be covered by.
The KKMS theorem says that for any KKMS covering, there is a balanced collection, such that the intersection of sets indexed by is nonempty:
It remains to explain what a "balanced collection" is. A collection of subsets of is called balanced if, for each subset, we can select a weight, such that, for each element, the sum of weights of all subsets that contain is exactly 1. For example, suppose. 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. Suppose we have a KKM covering, for. Construct a KKMS covering as follows:
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.
Reny and Wooders proved that the balanced set can also be chosen to be partnered.
Zhou proved a variant of the KKMS theorem where the covering consists of open sets rather than closed sets.

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.