Sperner's lemma

In mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which is equivalent to it.[1]

For the theorem in extremal set theory, see Sperner's theorem.

Sperner's lemma states that every Sperner coloring (described below) of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of 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. It is now believed to be an intractable computational problem to find a Brouwer fixed point or equivalently a Sperner coloring, even in the plane, in the general case. The problem is PPAD-complete, a complexity class invented by Christos Papadimitriou.

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

One-dimensional case

One-dimensional case example

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

Two-dimensional case example

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

Given a triangle ABC, and a triangulation T of the triangle, the set S of vertices of T is colored with three colors in such a way that

1. A, B, and C are colored 1, 2, and 3 respectively
2. Each vertex on an edge of ABC is to be colored only with one of the two colors of the ends of its edge. For example, each vertex on AC must have a color either 1 or 3.

Then there exists a triangle from T, whose vertices are colored with the three different colors. More precisely, there must be an odd number of such triangles.

Multidimensional case

In the general case the lemma refers to a n-dimensional simplex

${\displaystyle {\mathcal {A}}=A_{1}A_{2}\ldots A_{n+1}.}$

We consider a triangulation T which is a disjoint division of ${\displaystyle {\mathcal {A}}}$ into smaller n-dimensional simplices. Denote the coloring function as f : S → {1,2,3,...,n,n+1}, where S is again the set of vertices of T. The rules of coloring are:

1. The vertices of the large simplex are colored with different colors, i. e. f(A_i) = i for 1 ≤ i ≤ n+1.
2. Vertices of T located on any k-dimensional subface of the large simplex

${\displaystyle A_{i_{1}}A_{i_{2}}\ldots A_{i_{k+1}}}$

are colored only with the colors

${\displaystyle i_{1},i_{2},\ldots ,i_{k+1}.}$

Then there exists an odd number of simplices from T, whose vertices are colored with all n+1 colors. In particular, there must be at least one.

Proof

We shall first address the two-dimensional case. Consider a graph G built from the triangulation T as follows:

The vertices of G are the members of T 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 AB 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 AB, there must be an odd number of color changes in order to get different colors at the beginning and at the end). Therefore, the vertex of G 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 T.

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

Commentary

A simple two-dimensional triangulation of the example figure, colored and named in accordance with the assumptions of Sperner's Lemma

The graph derived from the example figure

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

One could add a new full-numbered triangle, say by inserting a node numbered 3 into the edge between 1 and 1 of node a, and joining that node to the other vertex of a. Doing so would have to create a pair of new nodes, like the situation with nodes f and g.

Generalizations

Subsets of labels

Suppose that each vertex of the triangulation may be labeled with multiple colors, so that the coloring function is f : 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 a hypergraph.

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. To illustrate, here are some balanced labeling examples for n=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 by Shapley in 1973.[2] It is a combinatorial analogue of the KKMS lemma.

Polytopes

Suppose that, instead of an ${\displaystyle n-1}$-dimensional simplex, we have a ${\displaystyle d}$-dimensional polytope with ${\displaystyle n}$ vertices.

Then there are at least ${\displaystyle n-d}$ fully labeled simplices, where "fully labeled" indicates that every label on the simplex has a different color. For example, if a (two-dimensional) polygon with n vertices is triangulated and colored according to the Sperner criterion, then there are at least ${\displaystyle n-2}$ fully labeled triangles.

The general statement was conjectured by Atanassov in 1996, who proved it for the case ${\displaystyle d=2}$.[3] The proof of the general case was first given by de Loera, Peterson, and Su in 2002.[4]

Permutations

Suppose that, instead of a single labeling, we have ${\displaystyle n}$ 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 ${\displaystyle n!}$ different pairs).

Then there are at least ${\displaystyle n!}$ fully labeled pairs. This was proved by Ravindra Bapat.[5]

Another way to state this lemma is as follows. Suppose there are ${\displaystyle n}$ 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 ${\displaystyle n!}$ such matchings. This can be used to find an envy-free cake-cutting with connected pieces.

Multiple labelings

Suppose that, instead of a single labeling, we have ${\displaystyle m}$ different Sperner labelings. Then:[6]^{:Thm 2.1}

1. For any positive integers ${\displaystyle k_{1},\ldots ,k_{m}}$whose sum is ${\displaystyle m+n-1}$, there exists a baby-simplex on which, for every ${\displaystyle i\in \{1,\ldots ,m\}}$, labeling number ${\displaystyle i}$ uses at least ${\displaystyle k_{i}}$ (out of ${\displaystyle n}$) distinct labels. Moreover, each label is used by at least one (out of ${\displaystyle m}$) labeling.
2. For any positive integers ${\displaystyle l_{1},\ldots ,l_{n}}$whose sum is ${\displaystyle m+n-1}$, there exists a baby-simplex on which, for every ${\displaystyle j\in \{1,\ldots ,n\}}$, the label ${\displaystyle j}$ is used by at least ${\displaystyle l_{j}}$ (out of ${\displaystyle m}$) different labelings.

Both versions reduce to Sperner's lemma when ${\displaystyle m=1}$, or when all ${\displaystyle m}$ labelings are identical.

See [7] for similar generalizations.

Degrees

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)

Suppose a triangle is triangulated and labeled with {1,2,3}. Consider the cyclic sequence of labels on the boundary of the triangle. Define the degree of the labeling as the difference between the number of switches from 1 to 2, and 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.[8] 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 cycles

There is a similar lemma about finite and infinite trees and cycles.[9]

Cubic Sperner lemma

A variant of Sperner's lemma on a cube (instead of a simplex) was proved by Harold W. Kuhn.[10] It is related to the Poincaré–Miranda theorem.[11]

Applications

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.

For this reason, 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.[12]

Sperner's lemma can be used to find a competitive equilibrium in an exchange economy, although there are more efficient ways to find it.[13]^:67

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

Equivalent results

There are several fixed-point theorems which come in three equivalent variants: an algebraic 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.[15]

Algebraic topology	Combinatorics	Set covering
Brouwer fixed-point theorem	Sperner's lemma	Knaster–Kuratowski–Mazurkiewicz lemma
Borsuk–Ulam theorem	Tucker's lemma	Lusternik–Schnirelmann theorem

See also

• Topological combinatorics

References

1. Flegg, H. Graham (1974). From Geometry to Topology. London: English University Press. pp. 84–89. ISBN 0-340-05324-0.
2. Shapley, L. S. (1973-01-01), Hu, T. C.; Robinson, Stephen M. (eds.), "On Balanced Games without Side Payments", Mathematical Programming, Academic Press, pp. 261–290, ISBN 978-0-12-358350-5, retrieved 2020-06-29
3. Atanassov, K. T. (1996), "On Sperner's lemma", Studia Scientiarum Mathematicarum Hungarica, 32 (1–2): 71–74, MR 1405126
4. De Loera, Jesus A.; Peterson, Elisha; Su, Francis Edward (2002), "A polytopal generalization of Sperner's lemma", Journal of Combinatorial Theory, Series A, 100 (1): 1–26, doi:10.1006/jcta.2002.3274, MR 1932067
5. Bapat, R. B. (1989). "A constructive proof of a permutation-based generalization of Sperner's lemma". Mathematical Programming. 44 (1–3): 113–120. doi:10.1007/BF01587081.
6. Meunier, Frédéric; Su, Francis Edward (2018-01-06). "Multilabeled versions of Sperner's and Fan's lemmas and applications". arXiv:1801.02044 [math.CO].
7. Asada, Megumi; Frick, Florian; Pisharody, Vivek; Polevy, Maxwell; Stoner, David; Tsang, Ling Hei; Wellner, Zoe (2018). "SIAM (Society for Industrial and Applied Mathematics)". SIAM Journal on Discrete Mathematics. 32: 591–610. arXiv:1701.04955. doi:10.1137/17m1116210.
8. Oleg R Musin (2014). "Around Sperner's lemma". arXiv:1405.7513 [math.CO].
9. Niedermaier, Andrew; Rizzolo, Douglas; Su, Francis Edward (2014), "A tree Sperner lemma", in Barg, Alexander; Musin, Oleg R. (eds.), Discrete Geometry and Algebraic Combinatorics, Contemporary Mathematics, 625, Providence, RI: American Mathematical Society, pp. 77–92, arXiv:0909.0339, doi:10.1090/conm/625/12492, ISBN 9781470409050, MR 3289406
10. Kuhn, H. W. (1960), "Some Combinatorial Lemmas in Topology", IBM Journal of Research and Development, 4 (5): 518–524, doi:10.1147/rd.45.0518
11. Michael Müger (2016), Topology for the working mathematician (PDF), Draft
12. Aigner, Martin; Ziegler, Günter M. (2010), "One square and an odd number of triangles", Proofs from The Book (4th ed.), Berlin: Springer-Verlag, pp. 131–138, doi:10.1007/978-3-642-00856-6_20, ISBN 978-3-642-00855-9
13. Scarf, Herbert (1967). "The Core of an N Person Game". Econometrica. 35 (1): 50–69. doi:10.2307/1909383. JSTOR 1909383.
14. Sperner, Emanuel (1980), "Fifty years of further development of a combinatorial lemma", Numerical solution of highly nonlinear problems (Sympos. Fixed Point Algorithms and Complementarity Problems, Univ. Southampton, Southampton, 1979), North-Holland, Amsterdam-New York, pp. 183–197, 199–217, MR 0559121
15. Nyman, Kathryn L.; Su, Francis Edward (2013), "A Borsuk–Ulam equivalent that directly implies Sperner's lemma", American Mathematical Monthly, 120 (4): 346–354, doi:10.4169/amer.math.monthly.120.04.346, MR 3035127

External links

• Proof of Sperner's Lemma at cut-the-knot
• Sperner's lemma and the Triangle Game, at the n-rich site.