## You are here

HomeKKM lemma

## Primary tabs

# 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 $\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. The union of the simplexes in $\mathcal{B}$ is $\mathcal{S}_{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 $|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, $\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.

## Mathematics Subject Classification

54H25*no label found*47H10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

new problem: Geometry by parag

Aug 24

new question: Scheduling Algorithm by ncovella

new question: Scheduling Algorithm by ncovella