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 (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 3 There 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.