Sperner's lemma

In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring of a triangulation of an simplex contains a cell whose vertices all have different colors.
The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root-finding algorithms, and are applied in fair division algorithms.
According to the Soviet Mathematical Encyclopaedia, a related 1929 theorem had also become known as the Sperner lemma – this point is discussed in the English translation. It is now commonly known as the Knaster–Kuratowski–Mazurkiewicz lemma.

Statement

One-dimensional case

In one dimension, Sperner's Lemma can be regarded as a discrete version of the intermediate value theorem. In this case, it essentially says that if a discrete function takes only the values 0 and 1, begins at the value 0 and ends at the value 1, then it must switch values an odd number of times.

Two-dimensional case

The two-dimensional case is the one referred to most frequently. It is stated as follows:
Subdivide a triangle arbitrarily into a triangulation consisting of smaller triangles meeting edge to edge. Then a Sperner coloring of the triangulation is defined as an assignment of three colors to the vertices of the triangulation such that

Each of the three vertices,, and of the initial triangle has a distinct color
The vertices that lie along any edge of triangle have only two colors, the two colors at the endpoints of the edge. For example, each vertex on must have the same color as or.

Then every Sperner coloring of every triangulation has at least one "rainbow triangle", a smaller triangle in the triangulation that has its vertices colored with all three different colors. More precisely, there must be an odd number of rainbow triangles.

Multidimensional case

In the general case the lemma refers to an -dimensional simplex:
Consider any triangulation, a disjoint division of into smaller -dimensional simplices, again meeting face-to-face. Denote the coloring function as:
where is the set of vertices of. A coloring function defines a Sperner coloring when:

The vertices of the large simplex are colored with different colors, that is, without loss of generality, for.
Vertices of located on any -dimensional subface of the large simplex
are colored only with the colors

Then every Sperner coloring of every triangulation of the -dimensional simplex has an odd number of instances of a rainbow simplex, meaning a simplex whose vertices are colored with all colors. In particular, there must be at least one rainbow simplex.

Proofs

Proof by induction

We shall first address the two-dimensional case. Consider a graph built from the triangulation as follows:
Note that on the interval there is an odd number of borders colored 1-2. On the intervals BC and CA, there are no borders colored 1-2 at all. Therefore, the vertex of corresponding to the outer area has an odd degree. But it is known that in a finite graph there is an even number of vertices with odd degree. Therefore, the remaining graph, excluding the outer area, has an odd number of vertices with odd degree corresponding to members of.
It can be easily seen that the only possible degree of a triangle from is 0, 1, or 2, and that the degree 1 corresponds to a triangle colored with the three colors 1, 2, and 3.
Thus we have obtained a slightly stronger conclusion, which says that in a triangulation there is an odd number of full-colored triangles.
A multidimensional case can be proved by induction on the dimension of a simplex. We apply the same reasoning, as in the two-dimensional case, to conclude that in a -dimensional triangulation there is an odd number of full-colored simplices.

Commentary

Here is an elaboration of the proof given previously, for a reader new to graph theory.
This diagram numbers the colors of the vertices of the example given previously. The small triangles whose vertices all have different numbers are shaded in the graph. Each small triangle becomes a node in the new graph derived from the triangulation. The small letters identify the areas, eight inside the figure, and area designates the space outside of it.
As described previously, those nodes that share an edge whose endpoints are numbered 1 and 2 are joined in the derived graph. For example, node shares an edge with the outer area, and its vertices all have different numbers, so it is also shaded. Node is not shaded because two vertices have the same number, but it is joined to the outer area.
One could add a new full-numbered triangle, say by inserting a node numbered 3 into the edge between 1 and 1 of node, and joining that node to the other vertex of. Doing so would have to create a pair of new nodes, like the situation with nodes and.

Proof without induction

Andrew McLennan and Rabee Tourky presented a different proof, using the volume of a simplex. It proceeds in one step, with no induction.

Computing a Sperner simplex

Suppose there is a d-dimensional simplex of side-length N, and it is triangulated into sub-simplices of side-length 1. There is a function that, given any vertex of the triangulation, returns its color. The coloring is guaranteed to satisfy Sperner's boundary condition. How many times do we have to call the function in order to find a rainbow simplex? Obviously, we can go over all the triangulation vertices, whose number is O, which is polynomial in N when the dimension is fixed. But, can it be done in time O, which is polynomial in the binary representation of N?
This problem was first studied by Christos Papadimitriou. He introduced a complexity class called PPAD, which contains this as well as related problems. He proved that finding a Sperner simplex is PPAD-complete even for d=3. Some 15 years later, Chen and Deng proved PPAD-completeness even for d=2. It is believed that PPAD-hard problems cannot be solved in time O.

Generalizations

Subsets of labels

Suppose that each vertex of the triangulation may be labeled with multiple colors, so that the coloring function is.
For every sub-simplex, the set of labelings on its vertices is a set-family over the set of colors. This set-family can be seen as a hypergraph.
If, for every vertex on a face of the simplex, the colors in are a subset of the set of colors on the face endpoints, then there exists a sub-simplex with a balanced labeling – a labeling in which the corresponding hypergraph admits a perfect fractional matching. To illustrate, here are some balanced labeling examples for :

- balanced by the weights.
- balanced by the weights .
- balanced by the weights.

This was proved by Shapley in 1973. It is a combinatorial analogue of the KKMS lemma.

Polytopal variants

Suppose that we have a -dimensional polytope with vertices. is triangulated, and each vertex of the triangulation is labeled with a label from Every main vertex is labeled. A sub-simplex is called fully-labeled if it is -dimensional, and each of its vertices has a different label. If every vertex in a face of is labeled with one of the labels on the endpoints of, then there are at least fully-labeled simplices. Some special cases are:

. In this case, is a simplex. The polytopal Sperner lemma guarantees that there is at least 1 fully-labeled simplex. That is, it reduces to Sperner's lemma.
. Suppose a two-dimensional polygon with vertices is triangulated and labeled using the labels such that, on each face between vertex and vertex, only the labels and are used. Then, there are at least sub-triangles in which three different labels are used.

The general statement was conjectured by Atanassov in 1996, who proved it for the case. The proof of the general case was first given by de Loera, Peterson, and Su in 2002. They provide two proofs: the first is non-constructive and uses the notion of pebble sets; the second is constructive and is based on arguments of following paths in graphs.
Meunier extended the theorem from polytopes to polytopal bodies, which need not be convex or simply-connected. In particular, if is a polytope, then the set of its faces is a polytopal body. In every Sperner labeling of a polytopal body with vertices, there are at least:
fully-labeled simplices such that any pair of these simplices receives two different labelings. The degree is the number of edges of to which belongs. Since the degree is at least, the lower bound is at least. But it can be larger. For example, for the cyclic polytope in 4 dimensions with vertices, the lower bound is:
Musin further extended the theorem to -dimensional piecewise-linear manifolds, with or without a boundary.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner further extended the theorem to pseudomanifolds with boundary, and improved the lower bound on the number of facets with pairwise-distinct labels.

Cubic variants

Suppose that, instead of a simplex triangulated into sub-simplices, we have an -dimensional cube partitioned into smaller -dimensional cubes.
Harold W. Kuhn proved the following lemma. Suppose the cube, for some integer, is partitioned into unit cubes. Suppose each vertex of the partition is labeled with a label from such that for every vertex : if then the label on is at most ; if then the label on is not. Then there exists a unit cube with all the labels . The special case is: suppose a square is partitioned into sub-squares, and each vertex is labeled with a label from The left edge is labeled with ; the bottom edge is labeled with or ; the top edge is labeled with or ; and the right edge is labeled with or . Then there is a square labeled with
Another variant, related to the Poincaré–Miranda theorem, is as follows. Suppose the cube is partitioned into unit cubes. Suppose each vertex is labeled with a binary vector of length, such that for every vertex : if then the coordinate of label on is 0; if then coordinate of the label on is 1; if two vertices are neighbors, then their labels differ by at most one coordinate. Then there exists a unit cube in which all labels are different. In two dimensions, another way to formulate this theorem is: in any labeling that satisfies conditions and, there is at least one cell in which the sum of labels is 0 .
Wolsey strengthened these two results by proving that the number of completely-labeled cubes is odd.
Musin extended these results to general quadrangulations.