display | more...

Sperner's Lemma is a lemma which was discovered by the German mathematician Emanuel Sperner. Its most significant application is in proving Brouwer's fixed point theorem, which states, basically, that given a continuous mapping of a triangle onto itself, there is at least one point (i.e. a "fixed point") which is mapped to itself. But one proof of Sperner's Lemma itself is one of the most beautiful proofs I have ever seen, and I will attempt to do it justice here.

The Lemma

Setting up the situation described by the lemma is a little complicated, so bear with me.

  • Start with a triangle in the plane.
  • Label the vertices with three different colors; let's use magenta, cyan and yellow here.
  • Now pick any finite number of points inside and on the edges of the triangle; it doesn't matter how many.
  • Triangulate the interior of the triangle using these points; in other words, draw segments connecting the points chosen in the previous step so that each point is a vertex of a triangle.
  • Now label each point with one of the three colors magenta, cyan or yellow. One caveat: any points on an edge of the big triangle can only be labeled with the colors with which the endpoints of that edge are labeled. So if a point is on the edge of the big triangle between the magenta and yellow vertices, it can only be labeled with magenta or yellow.
  • Sperner's lemma claims that there exists at least one small triangle (i.e. not the big triangle we started with) whose vertices are labeled with three different colors. This will be referred to as a "complete triangle."

Ponder this problem. It's one of those problems where you think it's got to be true, but damned if you know how to really prove it. And after all that, you'd think the proof would have to be a mess. You'd be wrong. Although it's not trivial, or even completely simple, it requires no advanced mathematical knowledge and can be explained without too much difficulty. It's not even a proof by contradiction, as many incredibly clever proofs are. I had a grin creeping across my face as I learned it for the first time in a class; you can tell it's going to be incredibly clever after about a fifth of the way in.

It may help to draw as you read the proof if you need to visualize something, but I hope I can explain things well enough that you won't have to. Without further ado...

The Proof

Note that zero is an even number. So if we can prove that the number of complete triangles is odd, that means there must be at least one of them, and so we will have a proof of the lemma.

Call a segment "good" if its endpoints are labeled with two different colors, and "bad" otherwise, and observe that, since its endpoints are all labeled with different colors, a good triangle has three good segments in it. On the other hand, an incomplete triangle has either zero good segments, if its vertices are all labeled with the same color; or two good segments, if it has two vertices labeled with the same color and one vertex labeled with a different color. There are no other possibilities.

Notice, then, that a complete triangle contains an odd number of good segments, and an incomplete triangle contains an even number of them. If there were an even number of complete triangles, then since even * odd = even and even * even = even, there would be an even number of good segments. So if we can add up the number of good segments in each small triangle and get an odd result, it means that there must be an odd number of complete triangles.

So we want to count the number of good segments in each triangle. But! Since the triangles can share edges, certain segments will be counted twice. Which? All segments in the interior of the big triangle are shared by two small triangles, so the only segments which won't be counted twice are the ones on the border of the big triangle. Which is to say, the segments that have both their endpoints on one of the edges of the big triangle.

The sum of the the number of good segments in each triangle, then, will look like this:

2 * (# of good interior segments) + (# of good boundary segments)

But the first term, because of the 2, will always be even! So in order to prove that the whole thing is odd, we only need to show that the second term, i.e. the number of good boundary segments, is odd. The end is near!

Pick a vertex of the big triangle; we are going to travel along an edge to another vertex. Every time we meet a point that has a different color than that of the point we just left, we've found a good segment. But! Since the two vertices at the end of the edge differ in color, we must do this an odd number of times. So each edge of the big triangle has an odd number of good segments along it. Since odd + odd + odd = odd, that means there are an odd number of good boundary edges. Working back up along the chain of implications we've been following, this means that the sum of the good segments in each small triangle is odd. This, in turn, means that there are an odd number of complete triangles, since complete triangles contain an odd number of good segments. If there are an odd number of complete triangles, it means there is at least one of them. Ta-da!

Was it Good for You?

Please /msg me if anything in my exposition was unclear.

Log in or register to write something here or to contact authors.