KKM lemma (original) (raw)

1 Preliminaries

We start by introducing some standard notation. ℝn+1is the (n+1)-dimensional real space with Euclidean normMathworldPlanetmath and metric. For a subset A⊂ℝn+1 we denote bydiam⁡(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,αi≥0 ∀i=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,αi≥0 ∀i=1,…,k}

Let ℰ={e1,e1,…,en+1} be the standardorthonormal 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αi⁢vi; 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 writeS⁢(V) then V is always a basis.

Let v be in S⁢(V), V={v1,v2,…,vk} a basis and vrepresented (uniquely) by barycentric coordinates(α1,α2,…,αk). We denote by FV⁢(v) the subset {j|αj≠0} of{1,2,…,k} (i.e., the set of non-null coordinates). LetI⊂{1,2,…,k}, the I-th face of S⁢(V) is the set{v∈S⁢(V)|FV⁢(v)⊆I}. A face of S⁢(V) is anI-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 byE the standard orthonormal basis forRn+1. Assume we have n+1 closed subsetsC1,…,Cn+1 of Sn with the property that for every subset I of {1,2,…,n+1} the following holds: theI-th face of Sn is a subset of ∪i∈ICi. 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 coupleD=(V,B); V are the vertices, a finite subset ofSn; 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. The union of the simplexes in ℬ is𝒮n.
    1. 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

A Sperner Coloring of D is an (n+1)-coloring C such that C⁢(v)∈Fℰ⁢(v) for every v∈V, that is, ifv 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 ofSn and C:V→{1,2,…,n+1} a Sperner Coloring of D. Then, there is a simplex S⁢(Vi)∈B such thatC⁢(Vi)={1,2,…,n+1}.

It is a standard result, for example by barycentric subdivisions, that 𝒮n has a sequence of simplicial subdivisionsD1,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 𝒮nas given in the lemma. We define the following functionγ:𝒮n→{1,2,…,n+1} as follows:

γ⁢(v)=min⁡{i|i∈Fℰ⁢(v)⁢ and ⁢v∈Ci}

γ is well defined by the hypothesisMathworldPlanetmath of the lemma andγ⁢(v)∈Fℰ⁢(v). Also, if γ⁢(v)=i thenv∈Ci. 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 everyj∈{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 inCj.

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

References