Sperner’s lemma

Let $ABC$ be a triangle, and let $S$ be the set of vertices of some triangulation $T$ of $ABC$. Let $f$ be a mapping of $S$ into a three-element set, say $\{1,2,3\}=T$ (indicated by red/green/blue respectively in the figure), such that:

• any point $P$ of $S$, if it is on the side $AB$, satisfies $f(P)\in \{1,2\}$

• similarly if $P$ is on the side $BC$, then $f(P)\in \{2,3\}$

• if $P$ is on the side $CA$, then $f(P)\in \{3,1\}$

(It follows that $f(A)=1,f(B)=2,f(C)=3$.) Then some (triangular) simplex of $T$, say $UVW$, satisfies

$$f(U)=1\mathit{\hspace{1em}\hspace{1em}}f(V)=2\mathit{\hspace{1em}\hspace{1em}}f(W)=3.$$

We will informally sketch a proof of a stronger statement: Let $M$ (resp. $N$) be the number of simplexes satisfying (1) and whose vertices have the same orientation as $ABC$ (resp. the opposite orientation). Then $M-N=1$ (whence $M>0$).

The proof is in the style of well-known proofs of, for example, Stokes’s theorem in the plane, or Cauchy’s theorems about a holomorphic function.

Define an antisymmetric function $d:T\times T\to \mathbb{Z}$ by

$$d(1,1)=d(2,2)=d(3,3)=0$$

$$d(1,2)=d(2,3)=d(3,1)=1$$

$$d(2,1)=d(3,2)=d(1,3)=-1.$$

Let’s define a “circuit” of size $n$ as an injective mapping $z$ of the cyclic group $\mathbb{Z}/n\mathbb{Z}$ into $V$ such that $z(n)$ is adjacent to $z(n+1)$ for all $n$ in the group.

Any circuit $z$ has what we will call a contour integral $Iz$, namely

$$Iz=\sum _{n}d(z(n),z(n+1)).$$

Let us say that two vertices $P$ and $Q$ are equivalent if $f(P)=f(Q)$.

There are four steps:

1) Contour integrals are added when their corresponding circuits are juxtaposed.

2) A circuit of size 3, hitting the vertices of a simplex $PQR$, has contour integral

• 0 if any two of $P$, $Q$, $R$ are equivalent, else

• +3 if they are inequivalent and have the same orientation as $ABC$, else

• -3

3) If $y$ is a circuit which travels around the perimeter of the whole triangle $ABC$, and with same orientation as $ABC$, then $Iy=3$.

4) Combining the above results, we get

$$3=\sum Iw=3M-3N$$

where the sum contains one summand for each simplex $PQR$.

Remarks: In the figure, $M=2$ and $N=1$: there are two “red-green-blue” simplexes and one blue-green-red.

With the same hypotheses as in Sperner’s lemma, there is such a simplex $UVW$ which is connected (along edges of the triangulation) to the side $AB$ (resp. $BC$,$CA$) by a set of vertices $v$ for which $f(v)\in \{1,2\}$ (resp. $\{2,3\}$, $\{3,1\})$. The figure illustrates that result: one of the red-green-blue simplexes is connected to the red-green side by a red-green “curve”, and to the other two sides likewise.

The original use of Sperner’s lemma was in a proof of Brouwer’s fixed point theorem in two dimensions.

Title	Sperner’s lemma
Canonical name	SpernersLemma
Date of creation	2013-03-22 13:44:33
Last modified on	2013-03-22 13:44:33
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	12
Author	mathcam (2727)
Entry type	Theorem
Classification	msc 55M20