Sperner’s Lemma

Posted on by

Sperner’s Lemma is an elegant result in discrete mathematics. While it originated in the context of combinatorics and graph colorings, it also has surprisingly powerful applications to analysis and topology. In particular, it provides a combinatorial proof of the Intermediate Value Theorem (below) and the Brouwer Fixed Point Theorem (next time). Its powerful continuous corollaries have earned it the nickname:

“The Discrete Mathematician’s Intermediate Value Theorem.”

To motivate the later and more technical definitions, let’s begin with a special case. Let T be a triangle that is triangulated into several smaller subtriangles, whose vertices are labelled either with a 1, 2, or 3.

The labeling chosen is special, in that:

  1. The main vertices of T are all given different labels.
  2. The label of a vertex along any edge of T matches the label of one of the main vertices spanning that edge.

For example: On the bottom-most edge between the corners labeled 1 and 2, each vertex in between is either labeled with a 1 or a 2. It is similarly the case for the edge whose corners are labeled 2 and 3, etc. The vertices on the inside are labeled arbitrarily.

Given any triangulation of T, a labeling that satisfies these conditions is called a Sperner labeling.

Sperner’s Lemma (Triangles) Any Sperner-labeled triangulation of T contains an odd number of elementary triangles possessing all labels.

Like most discrete existence theorems, it’s fun to play with it for awhile and try to convince yourself that you can’t find a counterexample. I should mention not all triangulations are admissible, only a simplicial subdivision – which I’ll explain below. Now that we have an intuition for what we are to prove, I’ll state it in its full generality. However, I will only furnish the proof of Sperner’s lemma for the triangle.

Definition. An n-dimensional simplex S is the convex hull of (n+1) affinely independent points in \mathbb{R}^{m} for m\ge n. We call these points the vertices of the simplex. For example, a 1-simplex is a line segment, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and so on. A k-face of an n-simplex is the convex hull of any (k+1)-subset of its vertices. An (n-1)-face of an n-simplex is called a facet. For example, the facets of a line segment are its endpoints, the facets of a triangle are its lines, and the facets of a tetrahedron are its triangular faces.

Definition. A simplicial subdivision of an n-simplex S is a collection of (distinct) smaller n-simplices whose union is S, with the property that any two of them intersect in a common face, or not at all. The smaller n-simplices are called subsimplices, and their vertices are called the vertices of the subdivision.

Definition. Let S be an n-simplex and number the facets of S by 1,2,\dots,n+1. Given a simplicial subdivision of S, a Sperner Labeling is any labeling of the vertices of the subdivision that satisfies:

  • Each vertex of the simplex is labeled by a distinct 1,2,\dots,n+1.
  • Each vertex on the boundary of S falling on the facet labeled j receives the label j. (You may label the interior vertices what you may).

Sperner’s Lemma. Any Sperner-labelled triangulation of a n-simplex must contain an odd number of fully labelled elementary n-simplices. In particular, there is at least one.

To test your understanding so far, it’s a good exercise to prove the case for n=1. I’ll prove it in the case of n=2. The higher dimensional cases follow by an induction argument, whose proof is more or less identical.

Proof. Let T be a triangle with a Sperner-labeled triangulation. Think of the triangle as a house, triangulated into triangular rooms. Let’s call every line-segment in the subdivision labeled 12 or 21 a “door” (labeled below).

asd

Notice that a fully labeled subtriangle only has one door and has two doors otherwise. This is because any room with at least one door has either no repeated labels (it is fully labeled), or out has one repeated label that appears twice. Since the triangulation is given a Sperner labeling, the only ways into the house from the outside is on facet whose corners are labeled 1 and 2. Thus, by Sperner’s Lemma for n=1, we know that there are an odd number of doors that lead from the outside to the inside.

Let’s start at any of the doors on the boundary and walk inside through the door. Either the room you’re in has another door for you to exit through, or there are no other doors. If there are no other doors, then you’re standing in a room with one door. So you’ve found a completely labeled room and we’ve proven existence. Otherwise, continue walking through doors into the one adjacent room, repeating this process (convince yourself why we can never double back on a room). Since the number of rooms is finite, the procedure must terminate and so at the end you’ve either found yourself outside or stopping somewhere inside. If you stop inside, then by the previous argument you’ve found your completely labeled room.


If you stop outside, then you’ve just paired up precisely two doors on the boundary of S that do not lead inside. However, since the number of boundary doors is odd, there must be at least one door that leads, and stays, inside. Proving the existence of at least one completely labeled room.

In fact, this shows that there are an odd number of boundary doors that locate a room inside. Moreover, any fully labelled rooms not reachable by paths from the boundary must come in pairs, since we can repeat the same process of walking about, which must terminate at some other room.

Let’s summarize our findings. There are an odd number of fully labeled rooms reachable from the outside doors. If there are fully labeled rooms unreachable from the boundary there are an even number of them.

Thus, there are an odd number of fully labeled rooms.

The continuous corollaries of Sperner’s Lemma are primarily deduced by devising a creative Sperner labeling, taking successive approximations, and exploiting compactness in some way or another. This process will be cleared up after the following result, but even clearer after proving the Brouwer Fixed Point Theorem in the next post.

Intermediate Value Theorem

Suppose f:\mathbb{R}\to \mathbb{R} is continuous. Suppose a,b\in \mathbb{R} and f(a)\le f(b). If c\in \mathbb{R} and f(a)< y< f(b), then there exists c\in (a,b) so that f(c)=y.

Proof. Suppose there exists no such c. Let T^1 be a partition of [a,b] with \text{mesh}(T^1)\le 2^{-1}. For each vertex x\in T^1, label

  • \lambda(x)=1 if f(x)<y and
  • \lambda(x)=2 if f(x)>y

Our initial assumption ensures this is a Sperner labeling. Hence there exists a completely labeled subinterval, call it [a_1,b_1] and assume without loss of generality that \lambda(a_1)=1 and \lambda(b_1)=2. We may assume this since, as we will see, the order of a_1 and b_1 don’t matter.

Let T^2 be a partition of [a_1,b_1] with \text{mesh}(T^2)<2^{-2}, and labeled as before. Then we can find a subinterval [a_2,b_2] that is completely labeled (again assuming without loss of generality that \lambda(a_2)=1, \lambda(b_2)=2). Continue by induction to furnish a sequence \{a_n\} and \{b_n\} so that \left|{b_n-a_n}\right|<2^{-n} so that \lambda(a_n)=1 and \lambda(b_n)=2. By compactness, each admits a convergent subsequence, and each convergent subsequence \{a_{n_{k}}\} and \{b_{n_{j}}\}. However, since \left|b_n-a_n\right|<2^{-n} for all n, it is clear that these two subsequences share a common limit, call it x. But then we see by the continuity of f(x) that

  • f(x)=f\left(\lim_{k\to \infty}a_{n_{k}}\right)=\lim_{k\to \infty}f(a_{n_{k}})\le y
  • f(x)=f\left(\lim_{j\to \infty}b_{n_{j}}\right)=\lim_{j\to \infty}f(b_{n_{j}})\ge y

So f(x)=y, as desired.

Thanks for reading. The definitions and proof of Sperner’s Lemma are due to Francis Su. The proof of the intermediate value theorem given here, to the best of my memory, is my own. Tomorrow I will deduce the Brouwer Fixed Point Theorem from Sperner’s Lemma.

2 thoughts on “Sperner’s Lemma”

  1. Pingback: An algebraic [and ninth] proof. | Alexander Adam Azzam

Leave a comment