Template:Short description Template:For
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.<ref>Template:Cite book</ref> It states that every Sperner coloring (described below) of a triangulation of an Template:Nowrap 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 (cake cutting) algorithms.
According to the Soviet Mathematical Encyclopaedia (ed. I.M. 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. M. Hazewinkel). It is now commonly known as the Knaster–Kuratowski–Mazurkiewicz lemma.
StatementEdit
One-dimensional caseEdit
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 caseEdit
The two-dimensional case is the one referred to most frequently. It is stated as follows:
Subdivide a triangle Template:Mvar 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 Template:Mvar, Template:Mvar, and Template:Mvar of the initial triangle has a distinct color
- The vertices that lie along any edge of triangle Template:Mvar have only two colors, the two colors at the endpoints of the edge. For example, each vertex on Template:Mvar must have the same color as Template:Mvar or Template:Mvar.
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 caseEdit
In the general case the lemma refers to a Template:Mvar-dimensional simplex:
- <math>\mathcal{A}=A_1 A_2 \ldots A_{n+1}.</math>
Consider any triangulation Template:Mvar, a disjoint division of <math>\mathcal{A}</math> into smaller Template:Mvar-dimensional simplices, again meeting face-to-face. Denote the coloring function as:
- <math>f:S\to\{1,2,3,\dots,n,n+1\},</math>
where Template:Mvar is the set of vertices of Template:Mvar. 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, Template:Math for Template:Math.
- Vertices of Template:Mvar located on any Template:Mvar-dimensional subface of the large simplex
<math>A_{i_1}A_{i_2}\ldots A_{i_{k+1}}</math>
are colored only with the colors
<math>i_1,i_2,\ldots,i_{k+1}.</math>
Then every Sperner coloring of every triangulation of the Template:Mvar-dimensional simplex has an odd number of instances of a rainbow simplex, meaning a simplex whose vertices are colored with all Template:Math colors. In particular, there must be at least one rainbow simplex.
ProofsEdit
Proof by inductionEdit
We shall first address the two-dimensional case. Consider a graph Template:Mvar built from the triangulation Template:Mvar as follows:
- The vertices of Template:Mvar are the members of Template:Mvar plus the area outside the triangle. Two vertices are connected with an edge if their corresponding areas share a common border with one endpoint colored 1 and the other colored 2.
Note that on the interval Template:Mvar there is an odd number of borders colored 1-2 (simply because A is colored 1, B is colored 2; and as we move along Template:Mvar, there must be an odd number of color changes in order to get different colors at the beginning and at the end). On the intervals BC and CA, there are no borders colored 1-2 at all. Therefore, the vertex of Template:Mvar corresponding to the outer area has an odd degree. But it is known (the handshaking lemma) 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 Template:Mvar.
It can be easily seen that the only possible degree of a triangle from Template:Mvar 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 Template:Mvar there is an odd number (and at least one) 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 Template:Mvar-dimensional triangulation there is an odd number of full-colored simplices.
CommentaryEdit
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 Template:Mvar 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 Template:Mvar shares an edge with the outer area Template:Mvar, and its vertices all have different numbers, so it is also shaded. Node Template:Mvar 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 Template:Mvar, and joining that node to the other vertex of Template:Mvar. Doing so would have to create a pair of new nodes, like the situation with nodes Template:Mvar and Template:Mvar.
Proof without inductionEdit
Andrew McLennan and Rabee Tourky presented a different proof, using the volume of a simplex. It proceeds in one step, with no induction.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref>Template:Cite journal</ref>
Computing a Sperner simplexEdit
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(Nd), which is polynomial in N when the dimension is fixed. But, can it be done in time O(poly(log N)), 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 (such as finding a Brouwer fixed point). 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.<ref>Template:Cite journal</ref> It is believed that PPAD-hard problems cannot be solved in time O(poly(log N)).
GeneralizationsEdit
Subsets of labelsEdit
Suppose that each vertex of the triangulation may be labeled with multiple colors, so that the coloring function is Template:Math.
For every sub-simplex, the set of labelings on its vertices is a set-family over the set of colors Template:Math. This set-family can be seen as a hypergraph.
If, for every vertex Template:Mvar on a face of the simplex, the colors in Template:Math 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 Template:Math:
- Template:Math - balanced by the weights Template:Math.
- Template:Math - balanced by the weights Template:Math.
- Template:Math - balanced by the weights Template:Math.
This was proved by Shapley in 1973.<ref>Template:Citation</ref> It is a combinatorial analogue of the KKMS lemma.
Template:AnchorPolytopal variantsEdit
Suppose that we have a Template:Mvar-dimensional polytope Template:Mvar with Template:Mvar vertices. Template:Mvar is triangulated, and each vertex of the triangulation is labeled with a label from Template:Math Every main vertex Template:Mvar is labeled Template:Mvar. A sub-simplex is called fully-labeled if it is Template:Mvar-dimensional, and each of its Template:Math vertices has a different label. If every vertex in a face Template:Mvar of Template:Mvar is labeled with one of the labels on the endpoints of Template:Mvar, then there are at least Template:Math fully-labeled simplices. Some special cases are:
- Template:Math. In this case, Template:Mvar 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.
- Template:Math. Suppose a two-dimensional polygon with Template:Mvar vertices is triangulated and labeled using the labels Template:Math such that, on each face between vertex Template:Mvar and vertex Template:Math, only the labels Template:Mvar and Template:Math are used. Then, there are at least Template:Math sub-triangles in which three different labels are used.
The general statement was conjectured by Atanassov in 1996, who proved it for the case Template:Math.<ref>Template:Citation</ref> The proof of the general case was first given by de Loera, Peterson, and Su in 2002.<ref>Template:Citation</ref> 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<ref>Template:Cite journal</ref> extended the theorem from polytopes to polytopal bodies, which need not be convex or simply-connected. In particular, if Template:Mvar is a polytope, then the set of its faces is a polytopal body. In every Sperner labeling of a polytopal body with vertices Template:Math, there are at least:
- <math>n - d - 1 + \left\lceil \frac{\min_{i=1}^n \deg_{B(P)}(v_i)}{d}\right\rceil</math>
fully-labeled simplices such that any pair of these simplices receives two different labelings. The degree Template:Math is the number of edges of Template:Math to which Template:Mvar belongs. Since the degree is at least Template:Mvar, the lower bound is at least Template:Math. But it can be larger. For example, for the cyclic polytope in 4 dimensions with Template:Mvar vertices, the lower bound is:
- <math>n - 4 - 1 + \left\lceil \frac{n-1}{4}\right\rceil \approx \frac{5}{4}n.</math>
Musin<ref>Template:Cite journal</ref> further extended the theorem to Template:Mvar-dimensional piecewise-linear manifolds, with or without a boundary.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner<ref name=":0">Template:Cite journal</ref> further extended the theorem to pseudomanifolds with boundary, and improved the lower bound on the number of facets with pairwise-distinct labels.
Cubic variantsEdit
Suppose that, instead of a simplex triangulated into sub-simplices, we have an Template:Mvar-dimensional cube partitioned into smaller Template:Mvar-dimensional cubes.
Harold W. Kuhn<ref name="k60">Template:Citation</ref> proved the following lemma. Suppose the cube Template:Math, for some integer Template:Mvar, is partitioned into Template:Mvar unit cubes. Suppose each vertex of the partition is labeled with a label from Template:Math such that for every vertex Template:Mvar: (1) if Template:Math then the label on Template:Mvar is at most Template:Mvar; (2) if Template:Math then the label on Template:Mvar is not Template:Mvar. Then there exists a unit cube with all the labels Template:Math (some of them more than once). The special case Template:Math is: suppose a square is partitioned into sub-squares, and each vertex is labeled with a label from Template:Math The left edge is labeled with Template:Math (= at most 1); the bottom edge is labeled with Template:Math or Template:Math (= at most 2); the top edge is labeled with Template:Math or Template:Math (= not 2); and the right edge is labeled with Template:Math or Template:Math (= not 1). Then there is a square labeled with Template:Math
Another variant, related to the Poincaré–Miranda theorem,<ref name="m15">Template:Citation</ref> is as follows. Suppose the cube Template:Math is partitioned into Template:Mvar unit cubes. Suppose each vertex is labeled with a binary vector of length Template:Mvar, such that for every vertex Template:Mvar: (1) if Template:Math then the coordinate Template:Mvar of label on Template:Mvar is 0; (2) if Template:Math then coordinate Template:Mvar of the label on Template:Mvar is 1; (3) if two vertices are neighbors, then their labels differ by at most one coordinate. Then there exists a unit cube in which all Template:Math labels are different. In two dimensions, another way to formulate this theorem is:<ref name=":1" /> in any labeling that satisfies conditions (1) and (2), there is at least one cell in which the sum of labels is 0 [a 1-dimensional cell with Template:Math and Template:Math labels, or a 2-dimensional cells with all four different labels].
Wolsey<ref>Template:Cite journal</ref> strengthened these two results by proving that the number of completely-labeled cubes is odd.
Musin<ref name=":1">Template:Citation</ref> extended these results to general quadrangulations.
Template:AnchorRainbow variantsEdit
Suppose that, instead of a single labeling, we have Template:Mvar different Sperner labelings. We consider pairs (simplex, permutation) such that, the label of each vertex of the simplex is chosen from a different labeling (so for each simplex, there are Template:Math different pairs). Then there are at least Template:Math fully labeled pairs. This was proved by Ravindra Bapat<ref name="b87">Template:Cite journal</ref> for any triangulation. A simpler proof, which only works for specific triangulations, was presented later by Su.<ref name="su1999">Template:Cite journal</ref>
Another way to state this lemma is as follows. Suppose there are Template:Mvar people, each of whom produces a different Sperner labeling of the same triangulation. Then, there exists a simplex, and a matching of the people to its vertices, such that each vertex is labeled by its owner differently (one person labels its vertex by 1, another person labels its vertex by 2, etc.). Moreover, there are at least Template:Math such matchings. This can be used to find an envy-free cake-cutting with connected pieces.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner<ref name=":0" /> extended this theorem to pseudomanifolds with boundary.
More generally, suppose we have Template:Mvar different Sperner labelings, where Template:Mvar may be different than Template:Mvar. Then:<ref>Template:Cite journal</ref>Template:Rp
- For any positive integers Template:Math whose sum is Template:Math, there exists a baby-simplex on which, for every Template:Math labeling number Template:Mvar uses at least Template:Mvar (out of Template:Mvar) distinct labels. Moreover, each label is used by at least one (out of Template:Mvar) labeling.
- For any positive integers Template:Mathwhose sum is Template:Math, there exists a baby-simplex on which, for every Template:Math, the label Template:Mvar is used by at least Template:Mvar (out of Template:Mvar) different labelings.
Both versions reduce to Sperner's lemma when Template:Math, or when all Template:Mvar labelings are identical.
See <ref>Template:Cite journal</ref> for similar generalizations.
Oriented variantsEdit
Sequence | Degree |
---|---|
123 | 1 (one 1-2 switch and no 2-1 switch) |
12321 | 0 (one 1-2 switch minus one 2-1 switch) |
1232 | 0 (as above; recall sequence is cyclic) |
1231231 | 2 (two 1-2 switches and no 2-1 switch) |
Brown and Cairns<ref>Template:Cite journal</ref> strengthened Sperner's lemma by considering the orientation of simplices. Each sub-simplex has an orientation that can be either +1 or -1 (if it is fully-labeled), or 0 (if it is not fully-labeled). They proved that the sum of all orientations of simplices is +1. In particular, this implies that there is an odd number of fully-labeled simplices.
As an example for Template:Math, suppose a triangle is triangulated and labeled with Template:Math Consider the cyclic sequence of labels on the boundary of the triangle. Define the degree of the labeling as the number of switches from 1 to 2, minus the number of switches from 2 to 1. See examples in the table at the right. Note that the degree is the same if we count switches from 2 to 3 minus 3 to 2, or from 3 to 1 minus 1 to 3.
Musin proved that the number of fully labeled triangles is at least the degree of the labeling.<ref name=m14>Template:Cite arXiv</ref> In particular, if the degree is nonzero, then there exists at least one fully labeled triangle.
If a labeling satisfies the Sperner condition, then its degree is exactly 1: there are 1-2 and 2-1 switches only in the side between vertices 1 and 2, and the number of 1-2 switches must be one more than the number of 2-1 switches (when walking from vertex 1 to vertex 2). Therefore, the original Sperner lemma follows from Musin's theorem.
Trees and cyclesEdit
There is a similar lemma about finite and infinite trees and cycles.<ref>Template:Citation</ref>
Related resultsEdit
Mirzakhani and Vondrak<ref>Template:Citation</ref> study a weaker variant of a Sperner labeling, in which the only requirement is that label i is not used on the face opposite to vertex i. They call it Sperner-admissible labeling. They show that there are Sperner-admissible labelings in which every cell contains at most 4 labels. They also prove an optimal lower bound on the number of cells that must have at least two different labels in each Sperner-admissible labeling. They also prove that, for any Sperner-admissible partition of the regular simplex, the total area of the boundary between the parts is minimized by the Voronoi partition.
ApplicationsEdit
Sperner colorings have been used for effective computation of fixed points. A Sperner coloring can be constructed such that fully labeled simplices correspond to fixed points of a given function. By making a triangulation smaller and smaller, one can show that the limit of the fully labeled simplices is exactly the fixed point. Hence, the technique provides a way to approximate fixed points. A related application is the numerical detection of periodic orbits and symbolic dynamics.<ref>Template:Cite journal</ref> Sperner's lemma can also be used in root-finding algorithms and fair division algorithms; see Simmons–Su protocols.
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.<ref>Template:Citation</ref>
Sperner's lemma can be used to find a competitive equilibrium in an exchange economy, although there are more efficient ways to find it.<ref>Template:Cite journal</ref>Template:Rp
Fifty years after first publishing it, Sperner presented a survey on the development, influence and applications of his combinatorial lemma.<ref>Template:Citation</ref>
Equivalent resultsEdit
Template:Analogous fixed-point theorems
See alsoEdit
ReferencesEdit
Template:Reflist <references responsive="0"/>
External linksEdit
- Proof of Sperner's Lemma at cut-the-knot
- Sperner's lemma and the Triangle Game, at the n-rich site.
- Sperner's lemma in 2D, a web-based game at itch.io.