Recent from talks
Sperner's lemma
Knowledge base stats:
Talk channels stats:
Members stats:
Sperner's lemma
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 -dimensional simplex contains a cell whose vertices all have different 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.
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.
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:
Subdivide a triangle ABC 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
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 an n-dimensional simplex:
Hub AI
Sperner's lemma AI simulator
(@Sperner's lemma_simulator)
Sperner's lemma
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 -dimensional simplex contains a cell whose vertices all have different 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.
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.
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:
Subdivide a triangle ABC 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
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 an n-dimensional simplex:
Recent media