Sperner's lemma
Encyclopedia
In mathematics
, Sperner's lemma is a combinatorial
analog
of the Brouwer fixed point theorem
, which follows from it. 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 point
s, in root-finding algorithm
s, 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
) has 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.
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.
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
Then there exists a triangle from T, whose vertices are colored with the three different colors. More generally, there must be an odd number of such triangles.
We consider a triangulation T which is a disjoint division of
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:
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.
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 2-dimensional case, to conclude that in a n-dimensional triangulation there is an odd number of full-colored simplices.
s with n vertices.. In that case, there are at least n-k fully labeled simplices, where k is the dimension of the polytope and "fully labeled" indicates that every label on the simplex has a different color. For example, if a polygon with n vertices is triangulated and colored according to the Sperner criterion, then there are at least n-2 fully labeled triangles. The general statement was conjectured by Atanassov
in 1996, who proved it for the case k=2. The proof of the general case was first given by de Loera, Peterson, and Su in 2002.
s. 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 algorithm
s and fair division
algorithms.
E. Sperner has presented the development, influence and applications of his combinatorial lemma
in [3].
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Sperner's lemma is a combinatorial
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
analog
Analogy
Analogy is a cognitive process of transferring information or meaning from a particular subject to another particular subject , and a linguistic expression corresponding to such a process...
of the Brouwer fixed point theorem
Brouwer fixed point theorem
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after Luitzen Brouwer. It states that for any continuous function f with certain properties there is a point x0 such that f = x0. The simplest form of Brouwer's theorem is for continuous functions f from a disk D to...
, which follows from it. Sperner's lemma states that every Sperner coloring (described below) of a triangulation of an n-dimensional simplex
Simplex
In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n-simplex is an n-dimensional polytope which is the convex hull of its n + 1 vertices. For example, a 2-simplex is a triangle, a 3-simplex is a tetrahedron,...
contains a cell colored with a complete set of colors. The initial result of this kind was proved by Emanuel Sperner
Emanuel Sperner
Emanuel Sperner was a German mathematician, best known for two theorems. He was born in Waltdorf , and died in Sulzburg-Laufen, Germany. He was a student at Hamburg University where his advisor was Wilhelm Blaschke...
, in relation with proofs of invariance of domain
Invariance of domain
Invariance of domain is a theorem in topology about homeomorphic subsets of Euclidean space Rn. It states:The theorem and its proof are due to L.E.J. Brouwer, published in 1912...
. Sperner colorings have been used for effective computation of fixed point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
s, in root-finding algorithm
Root-finding algorithm
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
s, and are applied in fair division
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
(cake cutting) algorithms.
According to the Soviet Mathematical Encyclopaedia (ed. I.M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk
Karol Borsuk
Karol Borsuk was a Polish mathematician.His main interest was topology.Borsuk introduced the theory of absolute retracts and absolute neighborhood retracts , and the cohomotopy groups, later called Borsuk-Spanier cohomotopy groups. He also founded the so called Shape theory...
and Mazurkiewicz
Stefan Mazurkiewicz
Stefan Mazurkiewicz was a Polish mathematician who worked in mathematical analysis, topology, and probability. He was a student of Wacław Sierpiński and a member of the Polish Academy of Learning...
) has 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.
One-dimensional case
Intermediate value theorem
In mathematical analysis, the intermediate value theorem states that for each value between the least upper bound and greatest lower bound of the image of a continuous function there is at least one point in its domain that the function maps to that value....
. In this case, it essentially says that if a discrete function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
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
Given a triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
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
- A, B and C are colored 1, 2 and 3 respectively
- 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 generally, there must be an odd number of such triangles.
Multidimensional case
In the general case the lemma refers to a n-dimensional simplexWe consider a triangulation T which is a disjoint division of
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:
- The vertices of the large simplex are colored with different colors, i. e. f(Ai) = i for 1 ≤ i ≤ n+1.
- Vertices of T located on any given k-dimensional subface
- are colored only with the colors
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
Handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that every finite undirected graph has an even number of vertices with odd degree...
) 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 2-dimensional case, to conclude that in a n-dimensional triangulation there is an odd number of full-colored simplices.
Generalizations
Sperner's lemma has been generalized to colorings of polytopePolytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
s with n vertices.. In that case, there are at least n-k fully labeled simplices, where k is the dimension of the polytope and "fully labeled" indicates that every label on the simplex has a different color. For example, if a polygon with n vertices is triangulated and colored according to the Sperner criterion, then there are at least n-2 fully labeled triangles. The general statement was conjectured by Atanassov
Krassimir Atanassov
Krassimir Todorov Atanassov is a Bulgarian mathematician. He is best known for launching the concepts of Generalized nets and Intuitionistic fuzzy sets, which are extensions of the concepts of Petri nets and Fuzzy sets, respectively...
in 1996, who proved it for the case k=2. The proof of the general case was first given by de Loera, Peterson, and Su in 2002.
Applications
Sperner colorings have been used for effective computation of fixed pointFixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
s. 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 algorithm
Root-finding algorithm
A root-finding algorithm is a numerical method, or algorithm, for finding a value x such that f = 0, for a given function f. Such an x is called a root of the function f....
s and fair division
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
algorithms.
E. Sperner has presented the development, influence and applications of his combinatorial lemma
in [3].
See also
- Brouwer fixed point theoremBrouwer fixed point theoremBrouwer's fixed-point theorem is a fixed-point theorem in topology, named after Luitzen Brouwer. It states that for any continuous function f with certain properties there is a point x0 such that f = x0. The simplest form of Brouwer's theorem is for continuous functions f from a disk D to...
- Borsuk–Ulam theoremBorsuk–Ulam theoremIn mathematics, the Borsuk–Ulam theorem, named after Stanisław Ulam and Karol Borsuk, states that every continuous function from an n-sphere into Euclidean n-space maps some pair of antipodal points to the same point....
- Tucker's lemma
- Topological combinatoricsTopological combinatoricsThe discipline of combinatorial topology used combinatorial concepts in topology and in the early 20th century this gradually turned into the field of algebraic topology....
External links
- Proof of Sperner's Lemma at cut-the-knotCut-the-knotCut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...