Sperner's lemma

lemma that every Sperner coloring of a triangulated simplex contains a properly colored simplex

Uses your system voice; voice and rate in settings.

≈ 9 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

  • DeutschLemma von Sperner
  • Françaislemme de Sperner
  • Italianolemma di Sperner
  • EnglishSperner's lemma
  • NederlandsSperner's lemma
  • РусскийЛемма Шпернера
  • עבריתהלמה של שפרנר
  • MagyarSperner-lemma

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 (described below) 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 to 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.

Statement

\mathcal{A}=A_1 A_2 \ldots A_{n+1}. Consider any triangulation , a disjoint division of \mathcal{A} into smaller -dimensional simplices, again meeting face-to-face. Denote the coloring function as: f:S\to\{1,2,3,\dots,n,n+1\}, 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 A_{i_1}A_{i_2}\ldots A_{i_{k+1}} are colored only with the colors i_1,i_2,\ldots,i_{k+1}.

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. 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.

It is believed that PPAD-hard problems cannot be solved in time O(poly(log N)).

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: n - d - 1 + \left\lceil \frac{\min_{i=1}^n \deg_{B(P)}(v_i)}{d}\right\rceil 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: n - 4 - 1 + \left\lceil \frac{n-1}{4}\right\rceil \approx \frac{5}{4}n. 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. 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 : (1) if then the label on is at most ; (2) if then the label on is not . Then there exists a unit cube with all the labels (some of them more than once).

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 (= at most 1); the bottom edge is labeled with or (= at most 2); the top edge is labeled with or (= not 2); and the right edge is labeled with or (= not 1). 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 : (1) if then the coordinate of label on is 0; (2) if then coordinate of the label on 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 labels are different.

In two dimensions, another way to formulate this theorem is: 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 and labels, or a 2-dimensional cells with all four different labels]. Wolsey strengthened these two results by proving that the number of completely-labeled cubes is odd.

Musin extended these results to general quadrangulations.

Rainbow variants

Suppose that, instead of a single labeling, we have 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 different pairs). Then there are at least fully labeled pairs.

This was proved by Ravindra Bapat for any triangulation. A simpler proof, which only works for specific triangulations, was presented later by Su. Another way to state this lemma is as follows.

Suppose there are 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 such matchings.

This can be used to find an envy-free cake-cutting with connected pieces. Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner extended this theorem to pseudomanifolds with boundary. More generally, suppose we have different Sperner labelings, where may be different than .

Then: For any positive integers whose sum is , there exists a baby-simplex on which, for every labeling number uses at least (out of ) distinct labels. Moreover, each label is used by at least one (out of ) labeling. For any positive integers whose sum is , there exists a baby-simplex on which, for every , the label is used by at least (out of ) different labelings.

Both versions reduce to Sperner's lemma when , or when all labelings are identical. See for similar generalizations.

Oriented variants

Brown and Cairns 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 , suppose a triangle is triangulated and labeled with 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.

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.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377905425 under CC BY-SA 4.0; modifications have been made.

Words in each sectionPolytopal variantsPolytopal variantsPolytopal variants: 672 words672Rainbow variantsRainbow variantsRainbow variants: 265 words265Oriented variantsOriented variantsOriented variants: 242 words242StatementStatementStatement: 222 words222
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot sperner-s-lemma-084071-ef50e9d1f6758e83 · hash ef50e9d1f6758e83648e63054a6dbfbbf9ea8e60f0b734d958718d925e373466 · captured 2026-10-01 · ledger · version history

Cite this page as: encyclopegia.org, “Sperner's lemma”, snapshot sperner-s-lemma-084071-ef50e9d1f6758e83. https://encyclopegia.org/a/sperner-s-lemma

Sources cited in this revision

9 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.