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 1Any continuous (for the unit ball in euclidean -space ) has a fixed point.

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

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

Now one way you could take this is to assume that 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 with a simplicial complex.

The ball is homeomorphic to the associated space of the simplicial complex , so it is enough to prove the fixed point theorem with replacing .

It is very easy to prove that every *simplicial* map has a fixed point: indeed, such a map corresponds to a map on the set of vertices

If is a bijection, then the barycenter will do. If not, there is an -face stable under , so we can use induction.

But the simplicial maps are far from being enough to approximate all continuous . Nonetheless, there is an important theorem that says that if you subdivide enough, then on the induced map of simplicial complexes

we have that 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 of the standard -simplex (homeomorphic to the -ball) onto its boundary. This is, as is well-known, equivalent to the Brouwer fixed point theorem. If there were such a retraction , then we could approximate it by a **simplicial map**

for a sufficiently fine subdivision of . This is a consequence of the simplicial approximation theorem.

We will now turn this into a discrete problem. First off, corresponds to a vertex map from the vertices of into the vertices of (i.e. the discrete set ). Indeed, by definition a simplicial map has to send vertices into vertices.

What does it mean for to be a simplicial approximation? It means that whenever is contained in a subsimplex of (that’s any sub-simplex, not necessarily one of the big faces), then so is . In particular, if is one of the vertices of , which can be considered as a vertex of and a vertex of and even a -simplex, we must have that

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

Let be a simplex of contained in a face of , say the -th face . Then as well since is a retraction and consequently is the identity on the boundary. It follows that since is a simplex and is a simplicial approximation. In particular, if are vertices of contained in the -th face of spanning the simplex , then cannot contain , for otherwise would intersect the th face . More generally, if are contained in the -face of spanned by the vertices corresponding to , then .

To reiterate, we will have a function from the vertices of to (a “coloring” of the vertices) such that:

- At the th vertex of (which is also a vertex of ), evaluates to .
- If are vertices contained in the -face of the full -simplex, then is a subset of .

The second condition implies the first, of course.

Moreover, we will have that any -simplex of is sent into , i.e. is a proper subsimplex of . Let us show that this is impossible.

Lemma 2 (Sperner)Let be a simplicial complex which is a subdivision of the -simplex .Let be a map from the vertices of to satisfying the above two conditions. Then the number of simplices of such that is (up to ordering) all of is odd: in particular, it is not zero.

*Proof:* We use induction on . Consider the collection of -simplices such that fills up precisely . These simplices necessarily lie in the specific -th face of the boundary by the conditions above.

Consider the collection of -simplices of which under fill up all of of . This is the set whose parity we want to determine. I claim that . Then we will be able to induct on .

We can count all the -simplices in by taking the boundaries of all the -simplices. Every -simplex is in the boundary of some -simplex, and by elementary geometry it follows that each -simplex is in the boundary of at most two -simplices. The ones that are in the boundary of precisely one -simplex are those that lie on .

To each -simplex , we assign a number , which is the number of -simplices in the boundary which map under to . Consider . Then, by the previous paragraph, this counts all the simplices which map under to , but counting everything not in the boundary twice. So

Now I claim that . Indeed, suppose is an -simplex of . If fills up all of , i.e. , then the map from the vertices of to is a bijection. Then because there is precisely one -simplex in the boundary which can map under to omit .

Otherwise, if , I claim that is either two or zero. If maps the vertices of to anything other than , then . If maps the vertices of to , then it is almost a bijection—there are two vertices that both go to the same element of . The only two -simplices in which are mapped by onto are those obtained by removing either or . So in this case.

These two remarks imply that if and only if , so that

We have proved the claim

It remains to see how this will lead to an inductive argument, and then to handle the base case. Now every simplex of is contained in the -simplex spanned by by the second condition. Also, induces a subdivision of . The statement of the lemma for is concerned precisely with this set , and it implies that precisely has odd cardinality. So does , and the inductive step is clear.

But we need to handle the base case. Consider ; let us prove the lemma in this case. A subdivision of the 1-simplex corresponds to a sequence

Here the simplices are . The map sends each to either or ; we have and . We need to show that the number of such that

is odd, for *any* such map from the to .

When , this is clear: only gets mapped that way. In general, we can use induction on and work upward by adding new vertices. This is an easy exercise.

**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 3There is no continuous retraction .

*Proof:* Indeed, by homeomorphism we would get a retraction . By subdividing into a some , we could get a simplicial approximation of . This simplicial approximation, call it , would correspond to a map from the vertices of to satisfying the conditions necessary for Sperner’s lemma. But the lemma implies that one of the -simplices of would be mapped onto the full -simplex and could not have image in . This contradiction establishes the Brouwer fixed-point theorem.

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.

September 23, 2010 at 11:19 am

I’ve read this in the lecture of Jacob Fox from Princeton.

Is there another proof of Brouwer Fixed Point Theorem ?

September 23, 2010 at 12:51 pm

The standard proof of this is to show that the inclusion admits no retraction because if there were, the map on homology would admit a retraction, hence would be injective. However, this is impossible by the standard computation of the homology of the sphere.

I believe this can be proved using transversality, but I can’t remember the proof.

October 10, 2011 at 5:25 pm

Hi

It was the exercise in Spanier that led me to your blog. I am an undergraduate student of Mathematics and the exercises in Simplicial Complexes in Spanier are really testing my patience…I have one small question as well. Spanier says that simplicial approximation to a continous map is an approximation is a sense that the induced continuous map between spaces is homotopic to the original continuous map. is there some other way in which is is an approximation? coz the definition for simplicial approx really isnt very intuitive to me… thnx

October 12, 2011 at 9:37 pm

I think, in practice, the fact that they are homotopic is the most important (e.g. it gives you a proof that the homotopy classes between finite simplicial complexes forma countable set). I’m not sure about anything else here.