KKM lemma

1 Preliminaries

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

The $n$-dimensional simplex ${𝒮}_n$ is the followingsubset 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 standardorthonormal basis of ${ℝ}^{n+1}$. So, ${𝒮}_n$ isthe simplex spanned by $ℰ$. Any element $v$ of $S(V)$ isrepresented 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 theset $V$ is in general position then the above representation isunique 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)$ thesubset $\{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 choiceof 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 forevery 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}}$ isnon-empty.

We prove the KKM Lemma by using Sperner’s Lemma; Sperner’s Lemmais 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$ ofsize $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 theintersection 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 thelargest 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$ suchthat $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 subsetof $V$ and $F_{ℰ}(e_i)=i$. Hence, If $C$ is a SpernerColoring 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 Coloringof $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 provethe 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 simplicialsubdivisions such that $|D_i|\to 0$. We set the color of everyvertex $v$ in $D_i$ to be $\gamma (v)$. This is a Sperner Coloringsince if $v$ is in $I$-fact then $\gamma (v)\in F_{ℰ}(v)\subseteq I$. Therefore, by Sperner’s Lemma we have in eachsubdivision $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 isan element of $S(V_i)$ and thus an element of ${𝒮}_n$).Since ${𝒮}_n$ is bounded and closed we get that $u_i$ hasa converging subsequence with a limit $L\in {𝒮}_n$. Now,every set $C_j$ is closed, and for every $ϵ>0$ we have anelement 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.∎