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.