KKM lemma

1 Preliminaries

We start by introducing some standard notation. ${ℝ}^{n+1}$ is the $(n+1)$-dimensional real space with Euclidean norm and metric. For a subset $A\subset {ℝ}^{n+1}$ we denote by $\mathrm{diam}(A)$ the diameter of $A$.

The $n$-dimensional simplex ${𝒮}_n$ is the following subset of ${ℝ}^{n+1}$

$$\left\{({\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_{n+1})\right|\sum _{i=1}^{n+1}{\alpha }_i=1,{\alpha }_i\ge 0\mathit{\hspace{1em}}\forall i=1,\mathrm{\dots },n+1\}$$

More generally, if $V=\{v_1,v_2,\mathrm{\dots },v_k\}$ is a set of vectors, then $S(V)$ is the simplex spanned by $V$:

$$S(V)=\{\sum _{i=1}^k{\alpha }_i{v}_i,|\sum _{i=1}^k{\alpha }_i=1,{\alpha }_i\ge 0\mathit{\hspace{1em}}\forall i=1,\mathrm{\dots },k\}$$

Let $ℰ=\{e_1,e_1,\mathrm{\dots },e_{n+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 coordinates $({\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_k)$ such that $v={\sum }_i{\alpha }_i{v}_i$; these are called a barycentric coordinates 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=\{v_1,v_2,\mathrm{\dots },v_k\}$ a basis and $v$ represented (uniquely) by barycentric coordinates $({\alpha }_1,{\alpha }_2,\mathrm{\dots },{\alpha }_k)$. We denote by $F_V(v)$ the subset $\{j|{\alpha }_j\ne 0\}$ of $\{1,2,\mathrm{\dots },k\}$ (i.e., the set of non-null coordinates). Let $I\subset \{1,2,\mathrm{\dots },k\}$, the $I$-th face of $S(V)$ is the set $\{v\in S(V)|F_V(v)\subseteq 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 ${\mathrm{S}}_n$ be the standard simplex spanned by $\mathrm{E}$ the standard orthonormal basis for ${\mathrm{R}}^{n\mathrm{+}\mathrm{1}}$. Assume we have $n\mathrm{+}\mathrm{1}$ closed subsets $C_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{C}_{n\mathrm{+}\mathrm{1}}$ of ${\mathrm{S}}_n$ with the property that for every subset $I$ of $\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{\dots }\mathrm{,}n\mathrm{+}\mathrm{1}\mathrm{\}}$ the following holds: the $I$-th face of ${\mathrm{S}}_n$ is a subset of ${\mathrm{\cup }}_{i\mathrm{\in }I}{C}_i$. Then, the intersection of the sets $C_{\mathrm{1}}\mathrm{,}{C}_{\mathrm{2}}\mathrm{,}\mathrm{\dots }\mathrm{,}{C}_{n\mathrm{+}\mathrm{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 coloring.

Definition 2 (Simplicial subdivision of ${\mathrm{S}}_n$).

A simplicial subdivision of ${\mathrm{S}}_n$ is a couple $D\mathrm{=}\mathrm{(}V\mathrm{,}\mathrm{B}\mathrm{)}$; $V$ are the vertices, a finite subset of ${\mathrm{S}}_n$; $\mathrm{B}$ is a set of simplexes $S\mathit{}\mathrm{(}{V}_{\mathrm{1}}\mathrm{)}\mathrm{,}S\mathit{}\mathrm{(}{V}_{\mathrm{2}}\mathrm{)}\mathrm{,}\mathrm{\dots }\mathrm{,}S\mathit{}\mathrm{(}{V}_k\mathrm{)}$ where each $V_i$ is a subset of $V$ of size $n\mathrm{+}\mathrm{1}$. $D$ has the following properties:

1. The union of the simplexes in $ℬ$ is ${𝒮}_n$.

2. If $S(V_i)$ and $S(V_j)$ intersect then the intersection is a face of both $S(V_i)$ and $S(V_j)$.

The norm of $D$, denoted by $\mathrm{|}D\mathrm{|}$, is the diameter of the largest simplex in $\mathrm{B}$.

An $(n+1)$-coloring of a subdivision $D=(V,ℬ)$ of ${𝒮}_n$ is a function

$$C:V\to \{1,2,\mathrm{\dots },n+1\}$$

A Sperner Coloring of $D$ is an $(n+1)$-coloring $C$ such that $C(v)\in F_{ℰ}(v)$ for every $v\in V$, 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_{ℰ}(e_i)=i$. Hence, If $C$ is a Sperner Coloring of $D$ then $C(e_i)=i$ for all $i=1,2,\mathrm{\dots },n+1$.

Theorem 3 (Sperner’s Lemma).

Let $D\mathrm{=}\mathrm{(}V\mathrm{,}\mathrm{B}\mathrm{)}$ be a simplicial subdivision of ${\mathrm{S}}_n$ and $C\mathrm{:}V\mathrm{\to }\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{\dots }\mathrm{,}n\mathrm{+}\mathrm{1}\mathrm{\}}$ a Sperner Coloring of $D$. Then, there is a simplex $S\mathit{}\mathrm{(}{V}_i\mathrm{)}\mathrm{\in }\mathrm{B}$ such that $C\mathit{}\mathrm{(}{V}_i\mathrm{)}\mathrm{=}\mathrm{\{}\mathrm{1}\mathrm{,}\mathrm{2}\mathrm{,}\mathrm{\dots }\mathrm{,}n\mathrm{+}\mathrm{1}\mathrm{\}}$.

It is a standard result, for example by barycentric subdivisions, that ${𝒮}_n$ has a sequence of simplicial subdivisions $D_1,D_2,\mathrm{\dots }$ such that $|D_i|\to 0$. We use this fact to prove the KKM Lemma:

Proof of KKM Lemma.

Let $C_1,C_2,\mathrm{\dots },C_{n+1}$ be closed subsets of ${𝒮}_n$ as given in the lemma. We define the following function $\gamma :{𝒮}_n\to \{1,2,\mathrm{\dots },n+1\}$ as follows:

$$\gamma (v)=\min \{i|i\in F_{ℰ}(v)\text{ and }v\in C_i\}$$

$\gamma$ is well defined by the hypothesis of the lemma and $\gamma (v)\in F_{ℰ}(v)$. Also, if $\gamma (v)=i$ then $v\in C_i$. Let $D_1,D_2,\mathrm{\dots }$ be a sequence of simplicial subdivisions such that $|D_i|\to 0$. We set the color of every vertex $v$ in $D_i$ to be $\gamma (v)$. This is a Sperner Coloring since if $v$ is in $I$-fact then $\gamma (v)\in F_{ℰ}(v)\subseteq I$. Therefore, by Sperner’s Lemma we have in each subdivision $D_i$ a simplex $S(V_i)$ such that $\gamma (V_i)=\{1,2,\mathrm{\dots },n+1\}$. Moreover, $\mathrm{diam}(S(V_i))\to 0$. By the properties of $\gamma$ for every $i=1,2,\mathrm{\dots }$ and every $j\in \{1,2,\mathrm{\dots },n+1\}$ we have that $S(V_i)\cap C_j\ne \varphi$. Let $u_i$ be the arithmetic mean of the elements of $V_i$ (this is an element of $S(V_i)$ and thus an element of ${𝒮}_n$). Since ${𝒮}_n$ is bounded and closed we get that $u_i$ has a converging subsequence with a limit $L\in {𝒮}_n$. Now, every set $C_j$ is closed, and for every $ϵ>0$ we have an element of $C_j$ of $ϵ$-distance from $L$; thus $L$ is in $C_j$.

Therefore, $L$ is in the intersection of all the sets $C_1,C_2,\mathrm{\dots },C_{n+1}$, and that proves the assertion. ∎

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