In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Sperner's lemma is a
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
result on colorings of
triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points.
Applications
In surveying
Specifically in surveying, triangulation involves only angle me ...
s,
analogous
Analogy (from Greek ''analogia'', "proportion", from ''ana-'' "upon, according to" lso "against", "anew"+ ''logos'' "ratio" lso "word, speech, reckoning" is a cognitive process of transferring information or meaning from a particular subject ...
to the
Brouwer fixed point theorem
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function f mapping a compact convex set to itself there is a point x_0 such that f(x_0)=x_0. The simplest ...
, 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
Emanuel Sperner (9 December 1905 – 31 January 1980) was a German mathematician, best known for two theorems. He was born in Waltdorf (near Neiße, Upper Silesia, now Nysa, Poland), and died in Sulzburg-Laufen, West Germany. He was a student at ...
, in relation with proofs of
invariance of domain
Invariance of domain is a theorem in topology about homeomorphic subsets of Euclidean space \R^n.
It states:
:If U is an open subset of \R^n and f : U \rarr \R^n is an injective continuous map, then V := f(U) is open in \R^n and f is a homeomorph ...
. Sperner colorings have been used for effective computation of
fixed points and in
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
s, and are applied in
fair division
Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inh ...
(cake cutting) algorithms. Finding a Sperner coloring or equivalently a Brouwer fixed point is now believed to be an intractable computational problem, even in the plane, in the general case. The problem is
PPAD-complete, a
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems of related resource-based computational complexity, complexity. The two most commonly analyzed resources are time complexity, time and spa ...
invented by
Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...
.
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 The Knaster–Kuratowski–Mazurkiewicz lemma is a basic result in mathematical fixed-point theory published in 1929 by Knaster, Kuratowski and Mazurkiewicz.
The KKM lemma can be proved from Sperner's lemma and can be used to prove the Brouwer f ...
.
Statement
One-dimensional case
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
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
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
The two-dimensional case is the one referred to most frequently. It is stated as follows:
Subdivide a
triangle
A triangle is a polygon with three Edge (geometry), edges and three Vertex (geometry), vertices. It is one of the basic shapes in geometry. A triangle with vertices ''A'', ''B'', and ''C'' is denoted \triangle ABC.
In Euclidean geometry, an ...
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 , , and of the initial triangle has a distinct color
# The vertices that lie along any edge of triangle have only two colors, the two colors at the endpoints of the edge. For example, each vertex on must have the same color as or .
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 case
In the general case the lemma refers to a -dimensional
simplex:
:
Consider any triangulation , a disjoint division of
into smaller -dimensional simplices, again meeting face-to-face. Denote the coloring function as:
:
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, i. e., for .
# Vertices of located on any -dimensional subface of the large simplex
are colored only with the colors
Then every Sperner coloring has an odd number of simplices its triangulation, whose vertices are colored with all colors. In particular, there must be at least one rainbow simplex.
Proof
![An illustration of the proof of Sperner's lemma in 2D](https://upload.wikimedia.org/wikipedia/commons/5/59/An_illustration_of_the_proof_of_Sperner%27s_lemma_in_2D.png)
We shall first address the two-dimensional case. Consider a graph built from the triangulation as follows:
:The vertices of are the members of 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 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 , 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 corresponding to the outer area has an odd degree. But it is known (the
handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom ...
) 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 .
It can be easily seen that the only possible degree of a triangle from 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 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 -dimensional triangulation there is an odd number of full-colored simplices.
Commentary
Here is an elaboration of the proof given previously, for a reader new to
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
.
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 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 shares an edge with the outer area , and its vertices all have different numbers, so it is also shaded. Node 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 , and joining that node to the other vertex of . Doing so would have to create a pair of new nodes, like the situation with nodes and .
Generalizations
Subsets of labels
Suppose that each vertex of the triangulation may be labeled with multiple colors, so that the coloring function is .
For every sub-simplex, the set of labelings on its vertices is a set-family over the set of colors . This set-family can be seen as a
hypergraph
In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
.
If, for every vertex on a face of the simplex, the colors in 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 :
* - balanced by the weights .
* - balanced by the weights .
* - balanced by the weights .
This was proved by
Shapley Shapley is a surname that might refer to one of the following:
* Lieutenant General Alan Shapley (1903–1973), of the U.S. Marine Corps, was a survivor the sinking of the USS Arizona in the attack on Pearl Harbor
* Harlow Shapley (1885–1972), Am ...
in 1973. It is a combinatorial analogue of the
KKMS lemma.
Polytopal variants
Suppose that we have a -dimensional
polytope
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
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
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
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
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
.
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:
:
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:
:
Musin further extended the theorem to -dimensional
piecewise-linear manifolds, with or without a boundary.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner
further exended the theorem to
pseudomanifold In mathematics, a pseudomanifold is a special type of topological space. It looks like a manifold at most of its points, but it may contain Mathematical singularity, singularities. For example, the cone of solutions of z^2=x^2+y^2 forms a pseudomani ...
s with boundary, and improved the lower bound on the number of facets with pairwise-distinct labels.
Cubic variants
Suppose that, instead of a simplex triangulated into sub-simplices, we have an -dimensional cube partitioned into smaller -dimensional cubes.
Harold W. Kuhn
Harold William Kuhn (July 29, 1925 – July 2, 2014) was an American mathematician who studied game theory. He won the 1980 John von Neumann Theory Prize along with David Gale and Albert W. Tucker. A former Professor Emeritus of Mathematics ...
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
In mathematics, the Poincaré–Miranda theorem is a generalization of intermediate value theorem, from a single function in a single dimension, to functions in dimensions. It says as follows:
::Consider n continuous functions of n variables, f_ ...
,
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
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
quadrangulation
In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unboun ...
s.
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
Ravindra B. Bapat is an Indian mathematician known for the Bapat–Beg theorem.
Education
He obtained B.Sc. from University of Mumbai, M.Stat. from the Indian Statistical Institute, New Delhi and Ph.D. from the University of Illinois at Chica ...
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
An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other sha ...
with connected pieces.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner
extended this theorem to
pseudomanifold In mathematics, a pseudomanifold is a special type of topological space. It looks like a manifold at most of its points, but it may contain Mathematical singularity, singularities. For example, the cone of solutions of z^2=x^2+y^2 forms a pseudomani ...
s 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.
Trees and cycles
There is a similar lemma about finite and infinite
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are u ...
and
cycles.
Related results
Mirzakhani and Vondrak 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.
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.
A related application is the numerical detection of
periodic orbit In mathematics, in the study of iterated functions and dynamical systems, a periodic point of a function is a point which the system returns to after a certain number of function iterations or a certain amount of time.
Iterated functions
Given a ...
s and
symbolic dynamics In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics (e ...
. Sperner's lemma can also be used in
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
s and
fair division
Fair division is the problem in game theory of dividing a set of resources among several people who have an entitlement to them so that each person receives their due share. That problem arises in various real-world settings such as division of inh ...
algorithms; see
Simmons–Su protocols The Simmons–Su protocols are several protocols for envy-free division. They are based on Sperner's lemma. The merits of these protocols is that they put few restrictions on the preferences of the partners, and ask the partners only simple querie ...
.
Sperner's lemma is one of the key ingredients of the proof of
Monsky's theorem
In geometry, Monsky's theorem states that it is not possible to dissect a square into an odd number of triangles of equal area. In other words, a square does not have an odd equidissection.
The problem was posed by Fred Richman in the '' American ...
, that a square cannot be cut into an odd number of
equal-area triangles.
Sperner's lemma can be used to find a
competitive equilibrium
Competitive equilibrium (also called: Walrasian equilibrium) is a concept of economic equilibrium introduced by Kenneth Arrow and Gérard Debreu in 1951 appropriate for the analysis of commodity markets with flexible prices and many traders, and s ...
in an
exchange economy, although there are more efficient ways to find it.
Fifty years after first publishing it, Sperner presented a survey on the development, influence and applications of his combinatorial lemma.
Equivalent results
See also
*
Topological combinatorics The mathematical discipline of topological combinatorics is the application of topological and algebro-topological methods to solving problems in combinatorics.
History
The discipline of combinatorial topology used combinatorial concepts in top ...
References
External links
Proof of Sperner's Lemmaat
cut-the-knot
Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...
Sperner's lemma and the Triangle Game at the n-rich site.
Sperner's lemma in 2D a web-based game at itch.io.
{{DEFAULTSORT:Sperner's Lemma
Combinatorics
Fixed points (mathematics)
Topology
Lemmas
Articles containing proofs
Fair division
Triangulation (geometry)