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
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after Luitzen Egbertus Jan Brouwer, L. E. J. (Bertus) Brouwer. It states that for any continuous function f mapping a nonempty compactness, compact convex set to itself, the ...
.
Statement
Let
be an
-dimensional
simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
with ''n''
vertices labeled as
.
A KKM covering is defined as a set
of
closed sets
In geometry, topology, and related branches of mathematics, a closed set is a set whose complement is an open set. In a topological space, a closed set can be defined as a set which contains all its limit points. In a complete metric space, a ...
such that for any
, the
convex hull
In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...
of the vertices corresponding to
is
covered
Cover or covers may refer to:
Packaging
* Another name for a lid
* Cover (philately), generic term for envelope or package
* Album cover, the front of the packaging
* Book cover or magazine cover
** Book design
** Back cover copy, part of ...
by
.
The KKM lemma says that in every KKM covering, the common intersection of all ''n'' sets is nonempty, i.e.:
:
Example
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.

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
Generalizations
Rainbow KKM lemma (Gale)
David Gale
David Gale (December 13, 1921 – March 7, 2008) was an American mathematician and economist. He was a professor emeritus at the University of California, Berkeley, affiliated with the departments of mathematics, economics, and industrial ...
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.:
:
.
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".
The rainbow KKM lemma can be proved using a
rainbow generalization of Sperner's lemma.
The original KKM lemma follows from the rainbow KKM lemma by simply picking ''n'' identical coverings.
Connector-free lemma (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
Ravindra B. Bapat is an Indian mathematician known for the Bapat–Beg theorem.
Education
He obtained B.Sc. from University of Mumbai, M.Stat. from the Indian Statistical Institute, New Delhi and Ph.D. from the University of Illinois at Chic ...
, generalizing
Sperner's lemma, 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
The KKMS theorem is a generalization of the KKM lemma by
Lloyd Shapley
Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Memorial Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally conside ...
. It is useful in
economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and interac ...
, especially in
cooperative game theory
In game theory, a cooperative game (or coalitional game) is a game with groups of players who form binding “coalitions” with external enforcement of cooperative behavior (e.g. through contract law). This is different from non-cooperative ...
.
While a KKM covering contains ''n'' closed sets, a KKMS covering contains
closed set
In geometry, topology, and related branches of mathematics, a closed set is a Set (mathematics), set whose complement (set theory), complement is an open set. In a topological space, a closed set can be defined as a set which contains all its lim ...
s - indexed by the nonempty subsets of