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.
The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain.
Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) had also become known as the Sperner lemma – this point is discussed in the English translation (ed.
In one dimension, Sperner's Lemma can be regarded as a discrete version of the intermediate value theorem.
In the general case the lemma refers to a n-dimensional simplex: Consider any triangulation T, a disjoint division of
But it is known (the handshaking lemma) that in a finite graph there is an even number of vertices with odd degree.
Thus we have obtained a slightly stronger conclusion, which says that in a triangulation T there is an odd number (and at least one) of full-colored triangles.
We apply the same reasoning, as in the two-dimensional case, to conclude that in a n-dimensional triangulation there is an odd number of full-colored simplices.
The small triangles whose vertices all have different numbers are shaded in the graph.
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 d shares an edge with the outer area i, and its vertices all have different numbers, so it is also shaded.
Node b is not shaded because two vertices have the same number, but it is joined to the outer area.
How many times do we have to call the function in order to find a rainbow simplex?
He introduced a complexity class called PPAD, which contains this as well as related problems (such as finding a Brouwer fixed point).
[4] It is believed that PPAD-hard problems cannot be solved in time O(poly(log N)).
If, for every vertex v on a face of the simplex, the colors in f(v) 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.
A sub-simplex is called fully-labeled if it is d-dimensional, and each of its d + 1 vertices has a different label.
[6] The proof of the general case was first given by de Loera, Peterson, and Su in 2002.
[7] 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.
For example, for the cyclic polytope in 4 dimensions with n vertices, the lower bound is: Musin[9] further extended the theorem to d-dimensional piecewise-linear manifolds, with or without a boundary.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner[10] further extended the theorem to pseudomanifolds with boundary, and improved the lower bound on the number of facets with pairwise-distinct labels.
Wolsey[14] strengthened these two results by proving that the number of completely-labeled cubes is odd.
A simpler proof, which only works for specific triangulations, was presented later by Su.
Suppose there are n people, each of whom produces a different Sperner labeling of the same triangulation.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner[10] extended this theorem to pseudomanifolds with boundary.
Brown and Cairns[19] strengthened Sperner's lemma by considering the orientation of simplices.
A Sperner coloring can be constructed such that fully labeled simplices correspond to fixed points of a given function.
A related application is the numerical detection of periodic orbits and symbolic dynamics.
Sperner's lemma is one of the key ingredients of the proof of Monsky's theorem, that a square cannot be cut into an odd number of equal-area triangles.
[25]: 67 Fifty years after first publishing it, Sperner presented a survey on the development, influence and applications of his combinatorial lemma.
