Sperner's lemma

If you take a glass of water and then shake it, it turns out that some point in the liquid will remain unmoved - this is known as a real world three dimensional example of the Brouwer fixed point theorem. However, as I once wrote in the past, this example works only if we assume that the matter is continues. If we start to think in terms of atoms, the theorem cannot be applied. While disappointing, it is not surprising. It is after all pretty obvious that a theorem that works with an infinite number of points will not work the same if we use instead a finite (but large) number. But what about the opposite? Can a theorem that is used to prove something about a finite number of objects be used to prove something about an infinite number of them?

The Sperner lemma is an example of such a case. This lemma is sometimes called a combinatorial analog of the Brouwer fixed point theorem. It is called so because it is rather simple to get the fixed point theorem for any dimension from the Sperner lemma for the same dimension. The two dimensional case is:

Given a triangle ABC, and a triangulation T of the triangle. The set S of vertices of T is colored with three colors in such a way that

1. A, B and C are colored 1, 2 and 3 respectively
2. Each vertex on an edge of ABC is to be colored only with one of the two colors of the ends of its edge. For example, each vertex on AC must have a color either 1 or 3.

Then there exists a triangle from T, whose vertices are colored with the three different colors. More generally, there must be an odd number of such triangles.

The general, n-th dimensional case, uses n-dimensional simplex instead of a triangle which is a 2D simplex.

There are a number of different proofs of the lemma, I personally know 3 of them. The usual idea is to show that the lemma works for the 2D space and then use induction to show that it works for all dimensions. While not difficult, this method of proof requires some thought and careful work. Interestingly enough there is also a proof that is both very short and doesn't require induction. It allows to prove the lemma for any given dimension in just one step. So for all those who prefer simple and easy proofs - read on:

To prove the lemma for the n-th dimension all we need to do is:
Let v be an inner vertice in T. Define a linear function of t that moves this vertice to the outer vertice of the same color when t goes from 0 to 1. The volume of any given simplex in T is the determinant of the vectors that correspond to the vertices of the simplex. Since all the vectors are linear functions of t, the volume is a polynomial of degree n. The sum of the volumes is thus also a polynomial of degree n. For t=0 the polynomial is obviously the volume of the outer simplex (for n=2 it is the volume of ABC). However if t is only slightly bigger then zero, we still have a triangulation so the sum of the volumes is the same and therefore the polynomial is a constant. For simplicity lets say that the volume is exactly 1. Now, when t=1 the volume of all the simplexes that are not colored in n colors becomes zero. On the other hand, the volumes of the other simplexes are either 1 or (-1) (depends on orientation). And with this we are done - if the sum of the volumes is 1 there are must be simplexes that have volume 1 but this is only possible if there is an odd number of simplexes with n colors.