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

Let $\Delta_d$ be a $d$-dimensional simplex with vertices labeled as $1,\ldots,d+1$. Suppose that $C_1,\ldots,C_{d+1}$ are closed sets such that for any $I \subseteq \{1,\ldots,d+1\}$, the convex hull of the vertices corresponding to $I$ is covered by $\bigcup_{i\in I}C_i$. Then $\bigcap_{i=1}^{d+1}C_i$ is nonempty.

Example

The two-dimensional case may serve as an illustration. In this case the simplex $\Delta_2$ is a triangle, whose vertices we can label 1, 2 and 3. We are given three closed sets $C_1,C_2,C_3$ which collectively cover the triangle; also we are told that $C_1$ covers vertex 1, $C_2$ covers vertex 2, $C_3$ covers vertex 3, and that the edge 12 (from vertex 1 to vertex 2) is covered by the sets $C_1$ and $C_2$, the edge 23 is covered by the sets $C_2$ and $C_3$, the edge 31 is covered by the sets $C_3$ and $C_1$. The KKM lemma states that the sets $C_1, C_2, C_3$ have at least one point in common.

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 can be reduced to the other result in its column.^[2]

Algebraic topology	Combinatorics	Set covering
Brouwer fixed-point theorem	Sperner's lemma	KKM lemma
Borsuk–Ulam theorem	Tucker's lemma	Lusternik–Schnirelmann theorem

References

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.
2. "A Borsuk–Ulam Equivalent that Directly Implies Sperner's Lemma". The American Mathematical Monthly 120 (4): 346. 2013. doi:10.4169/amer.math.monthly.120.04.346.

External links

• See the proof of KKM Lemma in Planet Math.