Sperner’s lemma

I found a proof of Sperner’s lemma that I am quite satisfied with a few months ago. I’ll repeat the proof here, but more importantly I’d like to share my thought process that lead to the proof.

What is Sperner’s lemma?

Look at the triangle below. It’s divided into smaller triangles, and each vertex is colored either red, green, or blue. The edges of the large triangle are each missing each of the three colors. Sperner’s lemma says this guarantees that there is a small triangle with a red vertex, a green vertex, and a blue vertex. Moreover, this can be generalized to simplices of any dimension.

For this type of problem, I find that it is usually helpful to consider the smaller dimensional cases. Things like this aren’t just coincidentally going to be true for arbitrary dimensions. It’s true for the same reason in every dimension, and it’s easier to see what is happening in the lower dimensions.

Here’s the 1-dimensional case. It’s more clear why it has to be true: there needs to be an odd number of edges (or 1-simplices) that have a blue and a green vertex in order to get from one side to the other side.

What about the 0-dimensional case? A 0-simplex is a vertex. So it’s trivially true in this case.

But it isn’t obvious how these generalize up to the 2-dimensional version. Why would this would be true?

Sphere idea

The first thing that stood out to me is that the condition requiring the edges to be missing a color felt unnatural. Especially if you go to higher dimensions, this condition becomes increasingly cumbersome. Is there a way to remove this, and make the problem more uniform?

In the 1-dimensional case, the obvious way to get rid of this is to loop things up in a circle. Now the problem is that we are no longer guaranteed to have a bicolored edge — all of the vertices might be colored blue, for example. But we can see why this can now happen: the boundary coloring simply becomes another bicolored edge when we loop it up.

So the circle version of Sperner’s lemma should guarantee that there are an even number of bicolored edges. Then the boundary condition states gives us one bicolored edge, from which we can infer that there must be at least one more.

Going back up to the 2-dimensional version, we would like to turn the boundary into another tricolored triangle so that we get a triangulated sphere. Then Sperner’s lemma should prove there are an even number of tricolored triangles.

If this picture doesn’t make sense to you, imagine that you are stretching open a tricolored triangle at the top of the sphere until you can see the rest of the sphere, and then flattening it out. The triangle you stretched open is the one with the new points and curved edges.

We’re now ready to state precisely what we intend to prove!

Sperner’s lemma (spherical form)

Take any triangulation of an -sphere. Color the vertices of the triangulation with colors in any way.
Then there will be an even number of -simplices with a vertex of every color.

Induction idea

The spherical viewpoint does make thinking about the problem a lot easier. We no longer have to worry about any distinctions between different vertices, beyond their colors. There are no vertices on the edge anymore — there is no edge! So we are now justified in considering approaches which handle each vertex in the same way. But how?

Now it’s helpful to start thinking about the fact this applies to arbitrary dimension. The easiest way for that to be true is if the lower dimensional cases imply the higher dimensional cases. This kind of proof is called proof by induction. We’ll start at the bottom and then climb from one rung of the latter to the one above.

First we have to make sure it is true for the smallest dimension, . In this case, there isn’t anything, which means there are zero -simplices which are colored with zero colors. Zero is an even number, so it actually turns out to be true in kind of a funky way.

For -dimensions, we need to know that a -dimensional sphere is simply two points. We have one color to work with, so both points have to be the same color. So there is an even number of -colored -simplices.

$$<p class="ql-center-picture"><img loading="lazy" src="http://adelelopez.com/wp-content/ql-cache/quicklatex.com-444917667f0c254449f29ebec9c50b25_l3.png" height="30" width="128" class="ql-img-picture quicklatex-auto-format" alt="Rendered by QuickLaTeX.com" title="Rendered by QuickLaTeX.com"/></p>$$

To see how we can climb, let’s consider the -dimension to -dimension case, since this is the easiest one for us to imagine and play with. If we look at a vertex from the middle of our original triangle, we can see that there is a circle of vertices surrounding it.

Unfortunately, the vertices on the circle might have three colors. If we wanted to use the 1-dimensional version of the lemma, we would need this circle to have only two different colors. But no one says you can’t recolor the vertices! If the circle has more than two colors, we’ll choose a color to replace with a different color. Let’s replace red with blue:

Now the circle has just two colors, and by the -dimensional case of Sperner’s lemma, we know that there will be an even number of bicolored edges. In this case, four:

We’ll call these 2-colored edges with no red vertices non-red edges. Similarly, any 2-colored edges with no blue will be non-blue edges. We’ll keep track of the number of these edges. Right now, and .

Remember those red vertices that we recolored blue? Let’s make those red again, one at a time, and watch what happens closely:

If the vertex that got recolored was part of any non-red edges, each of those edges now become non-blue. So now, and .

Now recolor the other one:

If the recolored vertex isn’t part of any non-red edges, then the number of non-red edges stays the same, and the number of non-blue edges stays the same. So and , as before.

The important thing to notice is that either way, the total number of non-red and non-blue edges stays the same, and is always even. . Now let’s put the center vertex back in:

Since the original vertex was blue, we now get a 3-colored simplex for every non-blue edge. Let’s use to count the number of 3-colored simplices when our vertex. So . If we recolor the center vertex to red, then we’ll get a 3-colored simplex for every non-red edge, but we’ll also lose all the 3-colored simplices we started with. So we’ll end up with .

The change in the number of 3-colored triangles is thus . Now notice that . We know is even, and is obviously even, so must always be even too! This is still going to be true even if we consider the whole thing, and not just the triangles around this vertex, because we’re already including all the triangles potentially affected by changing the color of this vertex.

Note now that recoloring a blue vertex to red was an arbitrary choice. That means we could change a vertex of any color to be any other color, and the same argument would be true. So no matter how much we recolor any of the vertices, we’ll always change the number of 3-colored triangles by an even number.

Finally, change all the vertices to be the same color. Now there are zero 3-colored vertices, and zero is an even number. Since recoloring only changed things by an even number, we must have started with an even number too!

We’re now ready to put this all in an official proof! Since I’ve explained all the basic ideas going into the proof above, I’m going to write the proof in a more rigorous style. I also am taking the liberty to strengthen the result a bit. The oriented version of this proof was by lbThingrb, which I have modified a bit here to emphasize similarity.

Sperner’s lemma

Take any finite triangulation of an -sphere. Color the vertices of the triangulation with colors in any way.
Then there will be an even number of -simplices with a vertex of every color.

Furthermore, if , then colored -simplices will have two possible orientations. There will be an equal number of such simplices with each orientation.

Proof

We’ll prove this by induction on , the number of dimensions.

In dimensions, there are two points which are both -colored. So it is true.
(NB: the original proof had a flaw in that while it is vacuously true for , the induction step doesn’t go through to the case because there’s nothing to control the number of vertices that appear in dimensions. So we have to use the fact that we know it is two here.)

Now assume it is true for -dimensions. We want to show that this implies it is true in -dimensions. So take a triangulation of an -sphere, and color the vertices with colors.

Take any vertex, and WLOG say it is colored blue. Consider the link of this vertex, which is an sphere, since an -sphere is a piecewise-linear -manifold. This sphere has a number of faces which are -colored without blue.

Since , we may choose a second color, call it red WLOG. Our link has a number of faces which are -colored without red.

We can recolor the red vertices on the link to be blue. When we recolor a vertex from red to blue, any -colored vertices without blue now become -colored vertices without red. Any other -colored vertices remain -colored vertices, with a different set of colors. So the sum remains the same.

Once all the vertices on the link have been recolored, , and by induction, is even. So must be even.

Now connect our link to the vertex it came from, forming a triangulated -ball. That vertex is blue, so the number of -colored simplices in the -ball is . If we recolor the center vertex to be red, the number of -colored vertices will be . All -simplices affected by recoloring this vertex are in the ball, so recoloring that vertex from blue to red changes the total number of -colored -simplices by .

Since is even, is even also. Since the vertex and colors were arbitrary, this means that any recoloring of any vertex changes the number of -colored -simplices by an even number.

Because the triangulation is finite, we may color every vertex to the same color. Then there are zero -colored -simplices, which is even.

Orientation

Now consider the oriented version. We have to start at since -simplices don’t have orientations. A triangulated -sphere is simply a polygon. This polygon is -colored and has an orientation. We can walk along in the direction of orientation, and count the number of blue to green edges and green to blue edges. Since we end back at the same color, we can see that we must have traversed an equal number of each orientation. So it is true for .

Proceeding as before, we choose a vertex which is blue WLOG. It’s link now has faces which are -colored without blue — with of one orientation and of the other. Specify the orientation of the faces by the orientation of the simplex with the center vertex. Similarly, it has faces which are -colored without red — and have one orientation and have the other orientation. Specify the orientation of these faces by the orientation of the simplex with the center vertex recolored red.

If we now recolor a vertex on the link from red to blue, a face becomes a face with a specific orientation, which one? If we reinsert the center vertex as specified above to determine the orientation, we can see that this recoloring is equivalent to a vertex swap. So it will have the opposite orientation. So faces become faces, and faces become faces. So and both remain the same as we recolor the vertices.

Once all the faces have been recolored, there are no more faces, so , and by induction, . So through recoloring, we maintain the equality .

When we reconnect the link to its center vertex, we get a triangulated -ball. Adding a vertex to the same side of each face will preserve the orientations. So there are -colored simplices in the ball, with of one orientation and of the other. If we recolor the vertex from blue to red, we instead have of one orientation and of the other. Thus the change is positively oriented -colored simplices is , and likewise, the change of the negatively oriented ones is . From before, we know that , which means that the numbers of each orientation change by the same amount.

Finally, since the triangulation is finite, we may color every vertex to the same color. Then there are equal numbers of -colored -simplices with each orientation: 0. Hence, the numbers of each orientation is always the same.

There’s an interesting extension of this proof. For , we can use the same proof to prove:
Take any finite triangulation of a closed, piecewise-linear -manifold. Color the vertices of the triangulation with colors in any way.
Then there will be an even number of -simplices with a vertex of every color.