KKM lemma


1 Preliminaries

We start by introducing some standard notation. n+1 is the (n+1)-dimensional real space with Euclidean normMathworldPlanetmath and metric. For a subset An+1 we denote by diam(A) the diameterMathworldPlanetmathPlanetmath of A.

The n-dimensional simplex 𝒮n is the following subset of n+1

{(α1,α2,,αn+1)|i=1n+1αi=1,αi0i=1,,n+1}

More generally, if V={v1,v2,,vk} is a set of vectors, then S(V) is the simplex spanned by V:

S(V)={i=1kαivi,|i=1kαi=1,αi0i=1,,k}

Let ={e1,e1,,en+1} be the standard orthonormal basis of n+1. So, 𝒮n is the simplex spanned by . Any element v of S(V) is represented by a vector of coordinatesMathworldPlanetmathPlanetmath (α1,α2,,αk) such that v=iαivi; these are called a barycentric coordinatesMathworldPlanetmath of v. If the set V is in general position then the above representation is unique and we say that V is a basis for S(V). If we write S(V) then V is always a basis.

Let v be in S(V), V={v1,v2,,vk} a basis and v represented (uniquely) by barycentric coordinates (α1,α2,,αk). We denote by FV(v) the subset {j|αj0} of {1,2,,k} (i.e., the set of non-null coordinates). Let I{1,2,,k}, the I-th face of S(V) is the set {vS(V)|FV(v)I}. A face of S(V) is an I-face for some I (note that this is independent of the choice of basis).

2 KKM Lemma

The main result we prove is the following:

Theorem 1 (Knaster-Kuratowski-Mazurkiewicz Lemma [1]).

Let Sn be the standard simplex spanned by E the standard orthonormal basis for Rn+1. Assume we have n+1 closed subsets C1,,Cn+1 of Sn with the property that for every subset I of {1,2,,n+1} the following holds: the I-th face of Sn is a subset of iICi. Then, the intersectionMathworldPlanetmath of the sets C1,C2,,Cn+1 is non-empty.

We prove the KKM Lemma by using Sperner’s Lemma; Sperner’s Lemma is based on the notion of simplicial subdivision and coloringMathworldPlanetmath.

Definition 2 (Simplicial subdivision of Sn).

A simplicial subdivision of Sn is a couple D=(V,B); V are the vertices, a finite subset of Sn; B is a set of simplexes S(V1),S(V2),,S(Vk) where each Vi is a subset of V of size n+1. D has the following properties:

  1. 1.

    The union of the simplexes in is 𝒮n.

  2. 2.

    If S(Vi) and S(Vj) intersect then the intersection is a face of both S(Vi) and S(Vj).

The norm of D, denoted by |D|, is the diameter of the largest simplex in B.

An (n+1)-coloring of a subdivision D=(V,) of 𝒮n is a function

C:V{1,2,,n+1}

A Sperner Coloring of D is an (n+1)-coloring C such that C(v)F(v) for every vV, that is, if v is on the I-th face then its color is from I. For example, if D=(V,) is a subdivision of the standard simplex 𝒮n then the standard basis is a subset of V and F(ei)=i. Hence, If C is a Sperner Coloring of D then C(ei)=i for all i=1,2,,n+1.

Theorem 3 (Sperner’s Lemma).

Let D=(V,B) be a simplicial subdivision of Sn and C:V{1,2,,n+1} a Sperner Coloring of D. Then, there is a simplex S(Vi)B such that C(Vi)={1,2,,n+1}.

It is a standard result, for example by barycentric subdivisions, that 𝒮n has a sequence of simplicial subdivisions D1,D2, such that |Di|0. We use this fact to prove the KKM Lemma:

Proof of KKM Lemma.

Let C1,C2,,Cn+1 be closed subsets of 𝒮n as given in the lemma. We define the following function γ:𝒮n{1,2,,n+1} as follows:

γ(v)=min{i|iF(v) and vCi}

γ is well defined by the hypothesisMathworldPlanetmath of the lemma and γ(v)F(v). Also, if γ(v)=i then vCi. Let D1,D2, be a sequence of simplicial subdivisions such that |Di|0. We set the color of every vertex v in Di to be γ(v). This is a Sperner Coloring since if v is in I-fact then γ(v)F(v)I. Therefore, by Sperner’s Lemma we have in each subdivision Di a simplex S(Vi) such that γ(Vi)={1,2,,n+1}. Moreover, diam(S(Vi))0. By the properties of γ for every i=1,2, and every j{1,2,,n+1} we have that S(Vi)Cjϕ. Let ui be the arithmetic mean of the elements of Vi (this is an element of S(Vi) and thus an element of 𝒮n). Since 𝒮n is bounded and closed we get that ui has a converging subsequence with a limit L𝒮n. Now, every set Cj is closed, and for every ϵ>0 we have an element of Cj of ϵ-distanceMathworldPlanetmath from L; thus L is in Cj.

Therefore, L is in the intersection of all the sets C1,C2,,Cn+1, and that proves the assertion. ∎

References

  • 1 B. Knaster, C. Kuratowski, and S. Mazurkiewicz, Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe, Fund. Math. 14 (1929) 132-137.
Title KKM lemma
Canonical name KKMLemma
Date of creation 2013-03-22 16:26:31
Last modified on 2013-03-22 16:26:31
Owner uriw (288)
Last modified by uriw (288)
Numerical id 14
Author uriw (288)
Entry type Theorem
Classification msc 54H25
Classification msc 47H10
Synonym K-K-M lemma
Related topic BrouwerFixedPointTheorem