Namespaces
Variants
Actions

Sperner lemma

From Encyclopedia of Mathematics
Revision as of 16:55, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

If a covering of a closed -dimensional simplex (cf. Simplex (abstract)) consists of closed sets that correspond to the vertices of in such a way that each face of this simplex is covered by the sets corresponding to its vertices, then there exists a point that belongs to all the sets . This lemma was established by E. Sperner (see [1]). Sperner's lemma implies that the Lebesgue dimension of the space is . 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 be an -dimensional simplex, let be a simplicial subdivision of and let be a mapping from (the vertex set of ) to such that whenever belongs to the face of . Then the number of -dimensional simplices in on which is surjective is odd.

A mapping like 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 was that for every the set should contain the point and that it should be disjoint from the face of opposite to . 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 -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