# KKM lemma

## 1 Preliminaries

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

The $n$-dimensional simplex $\mathcal{S}_{n}$ is the following subset of $\mathbb{R}^{n+1}$

 $\left\{(\alpha_{1},\alpha_{2},\ldots,\alpha_{n+1})\,\Big{|}\,\sum_{i=1}^{n+1}% \alpha_{i}=1,\quad\alpha_{i}\geq 0\quad\forall i=1,\ldots,n+1\right\}$

More generally, if $V=\{v_{1},v_{2},\ldots,v_{k}\}$ is a set of vectors, then $S(V)$ is the simplex spanned by $V$:

 $S(V)=\left\{\sum_{i=1}^{k}\alpha_{i}v_{i}\ ,\Big{|}\,\sum_{i=1}^{k}\alpha_{i}=% 1,\quad\alpha_{i}\geq 0\quad\forall i=1,\ldots,k\right\}$

Let $\mathcal{E}=\{e_{1},e_{1},\ldots,e_{n+1}\}$ be the standard orthonormal basis of $\mathbb{R}^{n+1}$. So, $\mathcal{S}_{n}$ is the simplex spanned by $\mathcal{E}$. Any element $v$ of $S(V)$ is represented by a vector of coordinates $(\alpha_{1},\alpha_{2},\ldots,\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},\ldots,v_{k}\}$ a basis and $v$ represented (uniquely) by barycentric coordinates $(\alpha_{1},\alpha_{2},\ldots,\alpha_{k})$. We denote by $F_{V}(v)$ the subset $\left\{j\,|\,\alpha_{j}\neq 0\right\}$ of $\{1,2,\ldots,k\}$ (i.e., the set of non-null coordinates). Let $I\subset\{1,2,\ldots,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 $\mathcal{S}_{n}$ be the standard simplex spanned by $\mathcal{E}$ the standard orthonormal basis for $\mathbb{R}^{n+1}$. Assume we have $n+1$ closed subsets $C_{1},\ldots,C_{n+1}$ of $\mathcal{S}_{n}$ with the property that for every subset $I$ of $\{1,2,\ldots,n+1\}$ the following holds: the $I$-th face of $\mathcal{S}_{n}$ is a subset of $\cup_{i\in I}C_{i}$. Then, the intersection of the sets $C_{1},C_{2},\ldots,C_{n+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 $\mathcal{S}_{n}$).

A simplicial subdivision of $\mathcal{S}_{n}$ is a couple $D=(V,\mathcal{B})$; $V$ are the vertices, a finite subset of $\mathcal{S}_{n}$; $\mathcal{B}$ is a set of simplexes $S(V_{1}),S(V_{2}),\ldots,S(V_{k})$ where each $V_{i}$ is a subset of $V$ of size $n+1$. $D$ has the following properties:

1. 1.

The union of the simplexes in $\mathcal{B}$ is $\mathcal{S}_{n}$.

2. 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 $|D|$, is the diameter of the largest simplex in $\mathcal{B}$.

An $(n+1)$-coloring of a subdivision $D=(V,\mathcal{B})$ of $\mathcal{S}_{n}$ is a function

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

A Sperner Coloring of $D$ is an $(n+1)$-coloring $C$ such that $C(v)\in F_{\mathcal{E}}(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,\mathcal{B})$ is a subdivision of the standard simplex $\mathcal{S}_{n}$ then the standard basis $\mathcal{E}$ is a subset of $V$ and $F_{\mathcal{E}}(e_{i})=i$. Hence, If $C$ is a Sperner Coloring of $D$ then $C(e_{i})=i$ for all $i=1,2,\ldots,n+1$.

###### Theorem 3 (Sperner’s Lemma).

Let $D=(V,\mathcal{B})$ be a simplicial subdivision of $\mathcal{S}_{n}$ and $C:V\to\{1,2,\ldots,n+1\}$ a Sperner Coloring of $D$. Then, there is a simplex $S(V_{i})\in\mathcal{B}$ such that $C(V_{i})=\{1,2,\ldots,n+1\}$.

It is a standard result, for example by barycentric subdivisions, that $\mathcal{S}_{n}$ has a sequence of simplicial subdivisions $D_{1},D_{2},\ldots$ such that $|D_{i}|\to 0$. We use this fact to prove the KKM Lemma:

###### Proof of KKM Lemma.

Let $C_{1},C_{2},\ldots,C_{n+1}$ be closed subsets of $\mathcal{S}_{n}$ as given in the lemma. We define the following function $\gamma:\mathcal{S}_{n}\to\{1,2,\ldots,n+1\}$ as follows:

 $\gamma(v)=\min\{i|i\in F_{\mathcal{E}}(v)\textrm{ and }v\in C_{i}\}$

$\gamma$ is well defined by the hypothesis of the lemma and $\gamma(v)\in F_{\mathcal{E}}(v)$. Also, if $\gamma(v)=i$ then $v\in C_{i}$. Let $D_{1},D_{2},\ldots$ 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_{\mathcal{E}}(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,\ldots,n+1\}$. Moreover, $\operatorname{diam}(S(V_{i}))\to 0$. By the properties of $\gamma$ for every $i=1,2,\ldots$ and every $j\in\{1,2,\ldots,n+1\}$ we have that $S(V_{i})\cap C_{j}\neq\phi$. 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 $\mathcal{S}_{n}$). Since $\mathcal{S}_{n}$ is bounded and closed we get that $u_{i}$ has a converging subsequence with a limit $L\in\mathcal{S}_{n}$. Now, every set $C_{j}$ is closed, and for every $\epsilon>0$ we have an element of $C_{j}$ of $\epsilon$-distance from $L$; thus $L$ is in $C_{j}$.

Therefore, $L$ is in the intersection of all the sets $C_{1},C_{2},\ldots,C_{n+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 KKMLemma 2013-03-22 16:26:31 2013-03-22 16:26:31 uriw (288) uriw (288) 14 uriw (288) Theorem msc 54H25 msc 47H10 K-K-M lemma BrouwerFixedPointTheorem