Namespaces
Variants
Actions

Difference between revisions of "Sperner lemma"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX)
 
Line 1: Line 1:
If a covering of a closed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866301.png" />-dimensional simplex (cf. [[Simplex (abstract)|Simplex (abstract)]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866302.png" /> consists of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866303.png" /> closed sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866304.png" /> that correspond to the vertices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866305.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866306.png" /> in such a way that each face <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866307.png" /> of this simplex is covered by the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866308.png" /> corresponding to its vertices, then there exists a point that belongs to all the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s0866309.png" />. This lemma was established by E. Sperner (see [[#References|[1]]]). Sperner's lemma implies that the [[Lebesgue dimension|Lebesgue dimension]] of the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663010.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663011.png" />. Sperner's lemma can also be used in a proof of Brouwer's fixed-point theorem and Brouwer's theorem on the invariance of domain (cf. [[Brouwer theorem|Brouwer theorem]]).
+
{{TEX|done}}
 +
If a covering of a closed $n$-dimensional simplex (cf. [[Simplex (abstract)|Simplex (abstract)]]) $T^n$ consists of $n+1$ closed sets $A_0,\dots,A_n$ that correspond to the vertices $a_0,\dots,a_n$ of $T^n$ in such a way that each face $T_r=(a_{i_0},\dots,a_{i_r})$ of this simplex is covered by the sets $A_{i_0},\dots,A_{i_r}$ corresponding to its vertices, then there exists a point that belongs to all the sets $A_0,\dots,A_n$. This lemma was established by E. Sperner (see [[#References|[1]]]). Sperner's lemma implies that the [[Lebesgue dimension|Lebesgue dimension]] of the space $\mathbf R^n$ is $n$. Sperner's lemma can also be used in a proof of Brouwer's fixed-point theorem and Brouwer's theorem on the invariance of domain (cf. [[Brouwer theorem|Brouwer theorem]]).
  
 
====References====
 
====References====
Line 9: Line 10:
 
The theorem stated in the main article above is not known as Sperner's lemma in the West, and, in fact, it is not proved in [[#References|[1]]].
 
The theorem stated in the main article above is not known as Sperner's lemma in the West, and, in fact, it is not proved in [[#References|[1]]].
  
Sperner's lemma is the following: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663012.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663013.png" />-dimensional simplex, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663014.png" /> be a simplicial subdivision of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663015.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663016.png" /> be a mapping from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663017.png" /> (the vertex set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663018.png" />) to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663019.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663020.png" /> whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663021.png" /> belongs to the face <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663022.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663023.png" />. Then the number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663024.png" />-dimensional simplices in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663025.png" /> on which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663026.png" /> is surjective is odd.
+
Sperner's lemma is the following: Let $\sigma=a_0\dots a_n$ be an $n$-dimensional simplex, let $T$ be a simplicial subdivision of $\sigma$ and let $f$ be a mapping from $V$ (the vertex set of $T$) to $\{0,\dots,n\}$ such that $f(v)\in\{i_0,\dots,i_k\}$ whenever $v$ belongs to the face $a_{i_0}\dots a_{i_k}$ of $\sigma$. Then the number of $n$-dimensional simplices in $T$ on which $f$ is surjective is odd.
  
A mapping like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663027.png" /> above is called a Sperner labelling. Sperner proved this lemma in [[#References|[1]]], and obtained as a consequence a somewhat weaker form of the theorem stated in the main article above: his requirement on the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663028.png" /> was that for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663029.png" /> the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663030.png" /> should contain the point <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663031.png" /> and that it should be disjoint from the face of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663032.png" /> opposite to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663033.png" />. This requirement readily implies the conditions stated in the item.
+
A mapping like $f$ above is called a Sperner labelling. Sperner proved this lemma in [[#References|[1]]], and obtained as a consequence a somewhat weaker form of the theorem stated in the main article above: his requirement on the sets $A_0,\dots,A_n$ was that for every $i$ the set $A_i$ should contain the point $a_i$ and that it should be disjoint from the face of $\sigma$ opposite to $a_i$. This requirement readily implies the conditions stated in the item.
  
 
The theorem stated in the main article above was proved by B. Knaster, K. Kuratowski and S. Mazurkiewicz in [[#References|[a2]]], where it was used to prove Brouwer's fixed-point theorem. This form of the theorem is also very useful in infinite-dimensional situations, see [[#References|[a1]]], and is sometimes called the KKM-theorem.
 
The theorem stated in the main article above was proved by B. Knaster, K. Kuratowski and S. Mazurkiewicz in [[#References|[a2]]], where it was used to prove Brouwer's fixed-point theorem. This form of the theorem is also very useful in infinite-dimensional situations, see [[#References|[a1]]], and is sometimes called the KKM-theorem.
Line 18: Line 19:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Dugundji,  A. Granas,  "Fixed point theory" , PWN  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  B. Knaster,  K. Kuratowski,  S. Mazurkiewicz,  "Ein Beweis des Fixpunktsatzes für <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s086/s086630/s08663034.png" />-dimensionale Simplexe"  ''Fund. Math.'' , '''14'''  (1929)  pp. 132–137</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H.E. Scarf,  "The approximation of fixed points of a continuous mapping"  ''SIAM J. Appl. Math.'' , '''15'''  (1967)  pp. 1328–1343</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.L. Allgower,  K. Georg,  "Simplicial and continuation methods for approximations to fixed points and solutions to systems of equations"  ''SIAM Review'' , '''22'''  (1980)  pp. 28–85</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B.C. Eaves,  "A short course in solving equations with PL homotopies" , ''Proc. SIAM-AMS'' , '''9''' , Amer. Math. Soc. &amp; SIAM  (1976)  pp. 73–143</TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Dugundji,  A. Granas,  "Fixed point theory" , PWN  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  B. Knaster,  K. Kuratowski,  S. Mazurkiewicz,  "Ein Beweis des Fixpunktsatzes für $n$-dimensionale Simplexe"  ''Fund. Math.'' , '''14'''  (1929)  pp. 132–137</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H.E. Scarf,  "The approximation of fixed points of a continuous mapping"  ''SIAM J. Appl. Math.'' , '''15'''  (1967)  pp. 1328–1343</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.L. Allgower,  K. Georg,  "Simplicial and continuation methods for approximations to fixed points and solutions to systems of equations"  ''SIAM Review'' , '''22'''  (1980)  pp. 28–85</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B.C. Eaves,  "A short course in solving equations with PL homotopies" , ''Proc. SIAM-AMS'' , '''9''' , Amer. Math. Soc. &amp; SIAM  (1976)  pp. 73–143</TD></TR></table>

Latest revision as of 19:01, 4 November 2014

If a covering of a closed $n$-dimensional simplex (cf. Simplex (abstract)) $T^n$ consists of $n+1$ closed sets $A_0,\dots,A_n$ that correspond to the vertices $a_0,\dots,a_n$ of $T^n$ in such a way that each face $T_r=(a_{i_0},\dots,a_{i_r})$ of this simplex is covered by the sets $A_{i_0},\dots,A_{i_r}$ corresponding to its vertices, then there exists a point that belongs to all the sets $A_0,\dots,A_n$. This lemma was established by E. Sperner (see [1]). Sperner's lemma implies that the Lebesgue dimension of the space $\mathbf R^n$ is $n$. Sperner's lemma can also be used in a proof of Brouwer's fixed-point theorem and Brouwer's theorem on the invariance of domain (cf. Brouwer theorem).

References

[1] E. Sperner, "Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes" Abh. Math. Sem. Univ. Hamburg , 6 (1928) pp. 265–272
[2] P.S. Aleksandrov, B.A. Pasynkov, "Introduction to dimension theory" , Moscow (1973) (In Russian)
[3] R. Engelking, "General topology" , Heldermann (1989)


Comments

The theorem stated in the main article above is not known as Sperner's lemma in the West, and, in fact, it is not proved in [1].

Sperner's lemma is the following: Let $\sigma=a_0\dots a_n$ be an $n$-dimensional simplex, let $T$ be a simplicial subdivision of $\sigma$ and let $f$ be a mapping from $V$ (the vertex set of $T$) to $\{0,\dots,n\}$ such that $f(v)\in\{i_0,\dots,i_k\}$ whenever $v$ belongs to the face $a_{i_0}\dots a_{i_k}$ of $\sigma$. Then the number of $n$-dimensional simplices in $T$ on which $f$ is surjective is odd.

A mapping like $f$ above is called a Sperner labelling. Sperner proved this lemma in [1], and obtained as a consequence a somewhat weaker form of the theorem stated in the main article above: his requirement on the sets $A_0,\dots,A_n$ was that for every $i$ the set $A_i$ should contain the point $a_i$ and that it should be disjoint from the face of $\sigma$ opposite to $a_i$. This requirement readily implies the conditions stated in the item.

The theorem stated in the main article above was proved by B. Knaster, K. Kuratowski and S. Mazurkiewicz in [a2], where it was used to prove Brouwer's fixed-point theorem. This form of the theorem is also very useful in infinite-dimensional situations, see [a1], and is sometimes called the KKM-theorem.

Sperner labellings, and Sperner's lemma on subdivisions as given above, have been used to develop effective ways to compute Brouwer fixed points, [a3], and hence such things as equilibria of economics, and, in turn, this development is at the basis of homology methods for the computation of roots of non-linear equations, etc., [a4], [a5].

References

[a1] J. Dugundji, A. Granas, "Fixed point theory" , PWN (1982)
[a2] B. Knaster, K. Kuratowski, S. Mazurkiewicz, "Ein Beweis des Fixpunktsatzes für $n$-dimensionale Simplexe" Fund. Math. , 14 (1929) pp. 132–137
[a3] H.E. Scarf, "The approximation of fixed points of a continuous mapping" SIAM J. Appl. Math. , 15 (1967) pp. 1328–1343
[a4] E.L. Allgower, K. Georg, "Simplicial and continuation methods for approximations to fixed points and solutions to systems of equations" SIAM Review , 22 (1980) pp. 28–85
[a5] B.C. Eaves, "A short course in solving equations with PL homotopies" , Proc. SIAM-AMS , 9 , Amer. Math. Soc. & SIAM (1976) pp. 73–143
How to Cite This Entry:
Sperner lemma. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sperner_lemma&oldid=11509
This article was adapted from an original article by I.G. Koshevnikova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article