There is an clever and interesting combinatorial (homology-free) approach to the proof of the well-known Brouwer fixed point theorem. Recall that this theorem states that:

Theorem 1 Any continuous ${f: B^n \rightarrow B^n}$ (for ${B^n}$ the unit ball in euclidean ${n}$-space ${\mathbb{R}^n}$) has a fixed point.

The first idea that suggests that a combinatorial approach might tackle the Brouwer theorem is that the set

$\displaystyle \left\{ f: B^n \rightarrow B^n \ \mathrm{with} \ \mathrm{no} \ \mathrm{fixed \ pt } \right\}$

is open in the set of continuous maps ${B^n \rightarrow B^n}$ (with the uniform topology). So if we can show that any continuous map ${f: B^n \rightarrow B^n}$ can be uniformly approximated by maps that do have fixed points to an arbitrary degree, then it will follow that ${f}$ itself has a fixed point.

Now one way you could take this is to assume that ${f}$ is differentiable. And indeed, there are differential-topological proofs of Brouwer’s theorem. This is not the purpose of the present post, though. We will replace the continuous ball ${B^n}$ with a simplicial complex.

The ball ${B^n}$ is homeomorphic to the associated space of the simplicial complex ${\Delta^n}$, so it is enough to prove the fixed point theorem with ${\Delta^n}$ replacing ${B^n}$.

It is very easy to prove that every simplicial map ${f: \Delta^n \rightarrow \Delta^n}$ has a fixed point: indeed, such a map corresponds to a map on the set of vertices

$\displaystyle f_s: \left\{0, 1, \dots, n\right\} \rightarrow \left\{0, 1, \dots, n\right\} .$

If ${f_s}$ is a bijection, then the barycenter will do. If not, there is an ${n-1}$-face stable under ${f}$, so we can use induction.

But the simplicial maps ${\Delta^n \rightarrow \Delta^n}$ are far from being enough to approximate all continuous ${f: \Delta^n \rightarrow \Delta^n}$. Nonetheless, there is an important theorem that says that if you subdivide ${\Delta^n}$ enough, then on the induced map of simplicial complexes

$\displaystyle \widetilde{\Delta^n} \rightarrow \Delta^n$

we have that ${f}$ can be “simplicially approximated” by a simplicial map. So if we can show that maps of this form have a fixed point, then we will be done with the Brouwer’s theorem. But in fact one proceeds in a slightly different way.

1. Sperner’s lemma

The actual combinatorial approach to the fixed point theorem proceeds by showing that there is no continuous retraction ${\Delta^n \rightarrow \partial \Delta^n}$ of the standard ${n}$-simplex (homeomorphic to the ${n}$-ball) onto its boundary. This is, as is well-known, equivalent to the Brouwer fixed point theorem. If there were such a retraction ${r: \Delta^n \rightarrow \partial \Delta^n}$, then we could approximate it by a simplicial map

$\displaystyle \widetilde{r}: K \rightarrow \partial \Delta^n$

for ${K}$ a sufficiently fine subdivision of ${\Delta^n}$. This is a consequence of the simplicial approximation theorem.

We will now turn this into a discrete problem. First off, ${\widetilde{r}}$ corresponds to a vertex map ${s}$ from the vertices of ${K}$ into the vertices of ${\partial \Delta^n}$ (i.e. the discrete set ${\left\{0, 1, \dots, n\right\}}$). Indeed, by definition a simplicial map has to send vertices into vertices.

What does it mean for ${\widetilde{r}: K \rightarrow \partial \Delta^n}$ to be a simplicial approximation? It means that whenever ${r(x)}$ is contained in a subsimplex of ${\partial \Delta^n}$ (that’s any sub-simplex, not necessarily one of the big faces), then so is ${\widetilde{r(x)}}$. In particular, if ${v}$ is one of the vertices of ${\Delta^n}$, which can be considered as a vertex of ${K}$ and a vertex of ${\partial \Delta^n}$ and even a ${0}$-simplex, we must have that

$\displaystyle s(v) = v.$

This is one condition. It is not the only one, however.

Let ${S }$ be a simplex of ${K}$ contained in a face of ${\partial \Delta^n}$, say the ${i}$-th face ${F_i}$. Then ${r(S) \subset F_i}$ as well since ${r}$ is a retraction and consequently is the identity on the boundary. It follows that ${\widetilde{r}(S) \subset F_i}$ since ${F_i}$ is a simplex and ${\widetilde{r}}$ is a simplicial approximation. In particular, if ${v_0, \dots, v_{n-1}}$ are vertices of ${K}$ contained in the ${i}$-th face of ${\partial \Delta^i}$ spanning the simplex ${S}$, then ${s(v_0), \dots, s(v_{n-1})}$ cannot contain ${i}$, for otherwise ${r(S)}$ would intersect the ${i}$th face ${F_i}$. More generally, if ${v_0, \dots, v_{k-1}}$ are contained in the ${k}$-face of ${\partial \Delta^n}$ spanned by the vertices corresponding to ${\left\{i_1, \dots, i_{k}\right\}}$, then ${\{s(v_0), \dots, s(v_k) \} \subset \left\{i_1, \dots, i_k\right\}}$.

To reiterate, we will have a function ${s}$ from the vertices of ${K}$ to ${\left\{0, 1, \dots, n\right\}}$ (a “coloring” of the vertices) such that:

1. At the ${i}$th vertex of ${\Delta^n}$ (which is also a vertex of ${K}$), ${s}$ evaluates to ${i}$.
2. If ${v_0, \dots, v_{k-1}}$ are vertices contained in the ${k}$-face ${\left\{i_1, \dots, i_k\right\}}$ of the full ${n}$-simplex, then ${s(v_1), \dots, s(v_{k-1})}$ is a subset of ${\left\{i_1, \dots, i_k\right\}}$.

The second condition implies the first, of course.

Moreover, we will have that any ${n}$-simplex of ${K}$ is sent into ${\partial \Delta^n}$, i.e. is a proper subsimplex of ${\Delta^n}$. Let us show that this is impossible.

Lemma 2 (Sperner) Let ${K}$ be a simplicial complex which is a subdivision of the ${n}$-simplex ${\Delta^n}$. Let ${s}$ be a map from the vertices of ${K}$ to ${\left\{0, 1, \dots, n\right\}}$ satisfying the above two conditions. Then the number of simplices ${(v_0, \dots, v_n)}$ of ${K}$ such that ${(s(v_0), \dots, s(v_n))}$ is (up to ordering) all of ${\left\{0, 1, \dots, n\right\}}$ is odd: in particular, it is not zero.

Proof: We use induction on ${n}$. Consider the collection ${C'}$ of ${n-1}$-simplices ${(v_0, \dots, v_{n}) \in \partial K}$ such that ${s(v_0), \dots, s(v_n)}$ fills up precisely ${\left\{0, 1, \dots, n-1\right\}}$. These simplices necessarily lie in the specific ${n}$-th face of the boundary by the conditions above.

Consider the collection ${C}$ of ${n}$-simplices of ${K}$ which under ${s}$ fill up all of of ${\left\{0, 1, \dots, n\right\}}$. This is the set whose parity we want to determine. I claim that ${|C| \equiv |C'| \mod 2}$. Then we will be able to induct on ${n}$.

We can count all the ${n-1}$-simplices in ${K}$ by taking the boundaries of all the ${n}$-simplices. Every ${n-1}$-simplex is in the boundary of some ${n}$-simplex, and by elementary geometry it follows that each ${n-1}$-simplex is in the boundary of at most two ${n}$-simplices. The ones that are in the boundary of precisely one ${n}$-simplex are those that lie on ${\partial K = \partial \Delta^{n-1}}$.

To each ${n}$-simplex ${c \in C}$, we assign a number ${f(c)}$, which is the number of ${n-1}$-simplices in the boundary ${\partial c}$ which map under ${s}$ to ${\left\{0, 1, \dots, n-1\right\}}$. Consider ${\sum_c f(c)}$. Then, by the previous paragraph, this counts all the ${n-1}$ simplices which map under ${s}$ to ${\left\{0, 1, \dots, n-1\right\}}$, but counting everything not in the boundary twice. So

$\displaystyle \sum_c f(c) \equiv |C'| \mod 2.$

Now I claim that ${\sum_c f(c) \equiv |C| \mod 2}$. Indeed, suppose ${c}$ is an ${n}$-simplex of ${K}$. If ${s(c)}$ fills up all of ${\left\{0, 1, \dots, n\right\}}$, i.e. ${c \in C}$, then the map from the vertices of ${c}$ to ${\left\{0, 1, \dots, n\right\}}$ is a bijection. Then ${f(c)=1}$ because there is precisely one ${n-1}$-simplex in the boundary which can map under ${s}$ to omit ${\{n\}}$.

Otherwise, if ${c \notin C}$, I claim that ${f(c)}$ is either two or zero. If ${f}$ maps the vertices of ${c}$ to anything other than ${\left\{0, 1, \dots, n-1\right\}}$, then ${f(c)=0}$. If ${f}$ maps the vertices of ${c}$ to ${\left\{0, 1, \dots, n-1\right\}}$, then it is almost a bijection—there are two vertices ${v_a, v_b}$ that both go to the same element of ${\left\{0, 1, \dots, n-1\right\}}$. The only two ${n-1}$-simplices in ${\partial c}$ which are mapped by ${s}$ onto ${\left\{0, 1, \dots, n-1\right\}}$ are those obtained by removing either ${v_a}$ or ${v_b}$. So ${f(c)=2}$ in this case.

These two remarks imply that ${f(c) \equiv 0 \mod 2}$ if and only if ${c \notin C}$, so that

$\displaystyle \sum_{c \in C} f(c) \equiv |C| \mod 2.$

We have proved the claim

$\displaystyle |C| \equiv |C'| \mod 2.$

It remains to see how this will lead to an inductive argument, and then to handle the base case. Now every simplex of ${C'}$ is contained in the ${n-1}$-simplex ${\Delta^{n-1}}$ spanned by ${\left\{0, 1, \dots, n-1\right\}}$ by the second condition. Also, ${K}$ induces a subdivision of ${\Delta^{n-1}}$. The statement of the lemma for ${n-1}$ is concerned precisely with this set ${C'}$, and it implies that precisely ${C'}$ has odd cardinality. So does ${C}$, and the inductive step is clear.

But we need to handle the base case. Consider ${n=1}$; let us prove the lemma in this case. A subdivision of the 1-simplex ${\Delta^1 = [0,1]}$ corresponds to a sequence

$\displaystyle 0=w_0 < \dots < w_R = 1.$

Here the simplices are ${[w_0, w_1], \dots, [w_{R-1}, w_R]}$. The map ${s}$ sends each ${w_i}$ to either ${0}$ or ${1}$; we have ${s(w_0)=0}$ and ${s(w_1)=1}$. We need to show that the number of ${i}$ such that

$\displaystyle s(\{w_i, w_{i+1}\}) = \left\{0,1\right\}$

is odd, for any such map from the ${\left\{w_i\right\}}$ to ${\left\{0,1\right\}}$.

When ${R=1}$, this is clear: only ${[w_0, w_1]}$ gets mapped that way. In general, we can use induction on ${R}$ and work upward by adding new vertices. This is an easy exercise.

$\Box$

2. The Brouwer fixed-point theorem

The details are now all essentially given for the proof of the Brouwer fixed-point theorem. We can prove the following variant:

Theorem 3 There is no continuous retraction ${r: B^n \rightarrow S^{n-1}}$.

Proof: Indeed, by homeomorphism we would get a retraction ${\Delta^n \rightarrow \partial \Delta^{n}}$. By subdividing ${\Delta^n}$ into a some ${K}$, we could get a simplicial approximation of ${K \rightarrow \partial \Delta^n}$. This simplicial approximation, call it ${\widetilde{r}}$, would correspond to a map from the vertices of ${K}$ to ${\left\{0, 1, \dots, n\right\}}$ satisfying the conditions necessary for Sperner’s lemma. But the lemma implies that one of the ${n}$-simplices of ${K}$ would be mapped onto the full ${n}$-simplex ${\Delta^n}$ and could not have image in ${\partial \Delta^n}$. This contradiction establishes the Brouwer fixed-point theorem. $\Box$

A slightly more general version of this material is an exercise in Spanier’s Algebraic Topology, and doing that problem was what led to this post.