Inmathematics,Sperner's lemma is acombinatorial result on colorings oftriangulations,analogous to theBrouwer fixed point theorem, which is equivalent to it.^[1] It states that everySperner coloring (described below) of a triangulation of an${\displaystyle n}$-dimensionalsimplex contains a cell whose vertices all have different colors.

The initial result of this kind was proved byEmanuel Sperner, in relation with proofs ofinvariance of domain. Sperner colorings have been used for effective computation offixed points and inroot-finding algorithms, and are applied infair division (cake cutting) algorithms.

According to the SovietMathematical Encyclopaedia (ed.I.M. Vinogradov), a related 1929 theorem (ofKnaster,Borsuk andMazurkiewicz) had also become known as theSperner lemma – this point is discussed in the English translation (ed. M. Hazewinkel). It is now commonly known as theKnaster–Kuratowski–Mazurkiewicz lemma.

In one dimension, Sperner's Lemma can be regarded as a discrete version of theintermediate value theorem. In this case, it essentially says that if a discretefunction 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.

The two-dimensional case is the one referred to most frequently. It is stated as follows:

Subdivide atriangleABC 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

1. Each of the three verticesA,B, andC of the initial triangle has a distinct color
2. The vertices that lie along any edge of triangleABC have only two colors, the two colors at the endpoints of the edge. For example, each vertex onAC must have the same color asA orC.

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.

In the general case the lemma refers to ann-dimensionalsimplex:

${\displaystyle \mathcal{A}=A_1{A}_2\dots A_{n+1}.}$

Consider any triangulationT, a disjoint division of${\displaystyle \mathcal{A}}$ into smallern-dimensional simplices, again meeting face-to-face. Denote the coloring function as:

${\displaystyle f:S\to \{1,2,3,\dots ,n,n+1\},}$

whereS is the set of vertices ofT. A coloring function defines a Sperner coloring when:

1. The vertices of the large simplex are colored with different colors, that is, without loss of generality,f(A_i) =i for1 ≤i ≤n + 1.
2. Vertices ofT located on anyk-dimensional subface of the large simplex

   ${\displaystyle A_{i_1}{A}_{i_2}\dots A_{i_{k+1}}}$

   are colored only with the colors

   ${\displaystyle i_1,i_2,\dots ,i_{k+1}.}$

Then every Sperner coloring of every triangulation of then-dimensionalsimplex has an odd number of instances of arainbow simplex, meaning a simplex whose vertices are colored with alln + 1 colors. In particular, there must be at least one rainbow simplex.

We shall first address the two-dimensional case. Consider a graphG built from the triangulationT as follows:

The vertices ofG are the members ofT 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 intervalAB there is an odd number of borders colored 1-2 (simply because A is colored 1, B is colored 2; and as we move alongAB, 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 ofG corresponding to the outer area has an odd degree. But it is known (thehandshaking 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 ofT.

It can be easily seen that the only possible degree of a triangle fromT 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 triangulationT 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 an-dimensional triangulation there is an odd number of full-colored simplices.

Here is an elaboration of the proof given previously, for a reader new tograph 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 areai 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, noded shares an edge with the outer areai, and its vertices all have different numbers, so it is also shaded. Nodeb 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 nodea, and joining that node to the other vertex ofa. Doing so would have to create a pair of new nodes, like the situation with nodesf andg.

Andrew McLennan and Rabee Tourky presented a different proof, using thevolume of a simplex. It proceeds in one step, with no induction.^[2][3]

Suppose there is ad-dimensional simplex of side-lengthN, 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(N^d), which is polynomial inN when the dimension is fixed. But, can it be done in time O(poly(logN)), which is polynomial in the binary representation of N?

This problem was first studied byChristos Papadimitriou. He introduced acomplexity class calledPPAD, which contains this as well as related problems (such as finding aBrouwer fixed point). He proved that finding a Sperner simplex isPPAD-complete even ford=3. Some 15 years later, Chen and Deng proved PPAD-completeness even ford=2.^[4] It is believed that PPAD-hard problems cannot be solved in time O(poly(logN)).

Suppose that each vertex of the triangulation may be labeled with multiple colors, so that the coloring function isF :S → 2^[n+1].

For every sub-simplex, the set of labelings on its vertices is a set-family over the set of colors[n + 1]. This set-family can be seen as ahypergraph.

If, for every vertexv on a face of the simplex, the colors inf(v) are a subset of the set of colors on the face endpoints, then there exists a sub-simplex with abalanced labeling – a labeling in which the correspondinghypergraph admits a perfect fractional matching. To illustrate, here are some balanced labeling examples forn = 2:

• ({1}, {2}, {3}) - balanced by the weights(1, 1, 1).
• ({1,2}, {2,3}, {3,1}) - balanced by the weights(1/2, 1/2, 1/2).
• ({1,2}, {2,3}, {1}) - balanced by the weights(0, 1, 1).

This was proved byShapley in 1973.^[5] It is a combinatorial analogue of theKKMS lemma.

Suppose that we have ad-dimensionalpolytopeP withn vertices.P is triangulated, and each vertex of the triangulation is labeled with a label from{1, …,n}. Every main vertexi is labeledi. A sub-simplex is calledfully-labeled if it isd-dimensional, and each of itsd + 1 vertices has a different label. If every vertex in a faceF ofP is labeled with one of the labels on the endpoints ofF, then there are at leastn –d fully-labeled simplices. Some special cases are:

• d =n – 1. In this case,P 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.
• d = 2. Suppose a two-dimensionalpolygon withn vertices is triangulated and labeled using the labels1, …,n such that, on each face between vertexi and vertexi + 1 (modn), only the labelsi andi + 1 are used. Then, there are at leastn – 2 sub-triangles in which three different labels are used.

The general statement was conjectured byAtanassov in 1996, who proved it for the cased = 2.^[6] The proof of the general case was first given by de Loera, Peterson, andSu in 2002.^[7] They provide two proofs: the first is non-constructive and uses the notion ofpebble sets; the second is constructive and is based on arguments of following paths ingraphs.

Meunier^[8] extended the theorem from polytopes topolytopal bodies, which need not be convex or simply-connected. In particular, ifP is a polytope, then the set of its faces is a polytopal body. In every Sperner labeling of a polytopal body with verticesv₁, …,v_n, there are at least:

${\displaystyle n-d-1+\lceil \frac{\underset{i=1}{\overset{n}{min}}{\mathrm{deg}}_{B(P)}(v_i)}{d}\rceil }$

fully-labeled simplices such that any pair of these simplices receives two different labelings. The degreedeg_B(P)(v_i) is the number of edges ofB(P) to whichv_i belongs. Since the degree is at leastd, the lower bound is at leastn –d. But it can be larger. For example, for thecyclic polytope in 4 dimensions withn vertices, the lower bound is:

${\displaystyle n-4-1+\lceil \frac{n-1}{4}\rceil \approx \frac{5}{4}n.}$

Musin^[9] further extended the theorem tod-dimensionalpiecewise-linear manifolds, with or without a boundary.

Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner^[10] further extended the theorem topseudomanifolds with boundary, and improved the lower bound on the number of facets with pairwise-distinct labels.

Suppose that, instead of a simplex triangulated into sub-simplices, we have ann-dimensional cube partitioned into smallern-dimensional cubes.

Harold W. Kuhn^[11] proved the following lemma. Suppose the cube[0,M]ⁿ, for some integerM, is partitioned intoMⁿ unit cubes. Suppose each vertex of the partition is labeled with a label from{1, …,n + 1}, such that for every vertexv: (1) ifv_i = 0 then the label onv is at mosti; (2) ifv_i=M then the label onv is noti. Then there exists a unit cube with all the labels{1, …,n + 1} (some of them more than once). The special casen = 2 is: suppose a square is partitioned into sub-squares, and each vertex is labeled with a label from{1,2,3}. The left edge is labeled with1 (= at most 1); the bottom edge is labeled with1 or2 (= at most 2); the top edge is labeled with1 or3 (= not 2); and the right edge is labeled with2 or3 (= not 1). Then there is a square labeled with1,2,3.

Another variant, related to thePoincaré–Miranda theorem,^[12] is as follows. Suppose the cube[0,M]ⁿ is partitioned intoMⁿ unit cubes. Suppose each vertex is labeled with a binary vector of lengthn, such that for every vertexv: (1) ifv_i = 0 then the coordinatei of label onv is 0; (2) ifv_i =M then coordinatei of the label onv 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 all2ⁿ labels are different. In two dimensions, another way to formulate this theorem is:^[13] 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(1,1) and(-1,-1) labels, or a 2-dimensional cells with all four different labels].

Wolsey^[14] strengthened these two results by proving that the number of completely-labeled cubes is odd.

Musin^[13] extended these results to generalquadrangulations.

Suppose that, instead of a single labeling, we haven 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 aren! different pairs). Then there are at leastn! fully labeled pairs. This was proved byRavindra Bapat^[15] for any triangulation. A simpler proof, which only works for specific triangulations, was presented later by Su.^[16]

Another way to state this lemma is as follows. Suppose there aren 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 leastn! such matchings. This can be used to find anenvy-free cake-cutting with connected pieces.

Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner^[10] extended this theorem topseudomanifolds with boundary.

More generally, suppose we havem different Sperner labelings, wherem may be different thann. Then:^{[17]: Thm 2.1}

1. For any positive integersk₁, …,k_m whose sum ism +n – 1, there exists a baby-simplex on which, for everyi ∈ {1, …,m}, labeling numberi uses at leastk_i (out ofn) distinct labels. Moreover, each label is used by at least one (out ofm) labeling.
2. For any positive integersI₁, …,I_mwhose sum ism +n – 1, there exists a baby-simplex on which, for everyj ∈ {1, …,n},, the labelj is used by at leastl_j (out ofm) different labelings.

Both versions reduce to Sperner's lemma whenm = 1, or when allm labelings are identical.

See^[18] for similar generalizations.

Brown and Cairns^[19] strengthened Sperner's lemma by considering theorientation 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 forn = 3, suppose a triangle is triangulated and labeled with{1,2,3}. Consider the cyclic sequence of labels on the boundary of the triangle. Define thedegree 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 thatthe number of fully labeled triangles is at least the degree of the labeling.^[20] 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.

There is a similar lemma about finite and infinitetrees andcycles.^[21]

Mirzakhani and Vondrak^[22] study a weaker variant of a Sperner labeling, in which the only requirement is that labeli is not used on the face opposite to vertexi. They call itSperner-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 theVoronoi partition.

Sperner colorings have been used for effective computation offixed 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 ofperiodic orbits andsymbolic dynamics.^[23] Sperner's lemma can also be used inroot-finding algorithms andfair division algorithms; seeSimmons–Su protocols.

Sperner's lemma is one of the key ingredients of the proof ofMonsky's theorem, that a square cannot be cut into an odd number ofequal-area triangles.^[24]

Sperner's lemma can be used to find acompetitive equilibrium in anexchange economy, although there are more efficient ways to find it.^[25]: 67

Fifty years after first publishing it, Sperner presented a survey on the development, influence and applications of his combinatorial lemma.^[26]

There are several fixed-point theorems which come in three equivalent variants: analgebraic topology variant, a combinatorial variant and a set-covering variant. Each variant can be proved separately using totally different arguments, but each variant can also be reduced to the other variants in its row. Additionally, each result in the top row can be deduced from the one below it in the same column.^[27]

• Topological combinatorics

• Proof of Sperner's Lemma atcut-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.

• Fixed-point theorems
• Combinatorics
• Topology
• Fair division
• Triangulation (geometry)

• Articles with short description
• Short description is different from Wikidata
• Articles containing proofs