Lemma from Sperner

The lemma Sperner often Spernersches Lemma called English Sperner's Lemma , is a mathematical result from the branch of topology . It goes back to the German mathematician Emanuel Sperner , who published it in 1928. The importance of the lemma is that with its help - and thus only by means of elementary combinatorial methods - a number of important mathematical theorems can be proven, such as Brouwer's fixed point theorem and related results or the theorem of the invariance of the open set and not least the Lebesgue plaster set .

Terminology in context

In the following, a Euclidean space of the finite dimension over the field of real numbers is taken as a basis. ${\displaystyle V}$ ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle \mathbb {R} }$

simplex

If one forms the convex hull of these points in given affine independent points ( ) , one obtains the n-simplex . The names of the vertices or corners of the associated n-simplex and its dimension . The following is also written for the set of vertices of the n-simplex . ${\displaystyle V}$ ${\displaystyle n+1}$ ${\displaystyle x_{0},\,\ldots ,\,x_{n}}$ ${\displaystyle n\in \mathbb {N} ,n\leq m}$ ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})\subset V}$ ${\displaystyle x_{0},\,\ldots ,\,x_{n}}$ ${\displaystyle n}$ ${\displaystyle \{x_{0},\,\ldots ,\,x_{n}\}}$ ${\displaystyle \Delta }$ ${\displaystyle E(\Delta )}$

Side of a simplex

If one forms the convex hull in the same way for a subset with , one obtains a sub- simplex , which is called the (r-dimensional) side of . ${\displaystyle \{x_{i_{0}},\,\ldots ,\,x_{i_{r}}\}\subseteq \{x_{0},\,\ldots ,\,x_{n}\}}$ ${\displaystyle 0\leq i_{1}<\dots <i_{r}\leq n}$ ${\displaystyle {\Delta }^{*}=\Delta ({x_{i_{0}},\,\ldots ,\,x_{i_{r}}})\subseteq \Delta }$ ${\displaystyle \Delta }$

Simplicial complex and set of corners

A (finite) simplicial complex in Euclidean space is a family of simplexes of with the following properties: ${\displaystyle V}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {V}}}$

1. With every simplex , every side of belongs to . ${\displaystyle {{\Delta }^{*}}\in {\mathcal {K}}}$ ${\displaystyle {{\Delta }^{*}}}$ ${\displaystyle {\mathcal {K}}}$
2. The intersection of two simplexes of is empty or a common side of both simplexes . ${\displaystyle {{\Delta }^{*}}_{1}\cap {{\Delta }^{*}}_{2}}$ ${\displaystyle {{\Delta }^{*}}_{1},\,{{\Delta }^{*}}_{2}\in {\mathcal {K}}}$ ${\displaystyle {{\Delta }^{*}}_{1},\,{{\Delta }^{*}}_{2}}$
3. ${\displaystyle {\mathcal {K}}}$is a finite set .

The family of sides of an n-simplex always forms a finite simplicial complex . ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})\subset V}$

If one forms the union , then one obtains the vertex set of , namely the set of all vertices of the simplexes occurring in. ${\displaystyle E=E({\mathcal {K}})=\bigcup _{{{\Delta }^{*}}\in {\mathcal {K}}}E({\Delta }^{*})}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$

Polyhedron and triangulation

The union formed over all simplexes of a simplicial complex , it is called to corresponding polyhedra and its triangulation . One then says that the polyhedron is triangulated by . Since it is assumed here that there is a finite family, such a polyhedron is always a compact subset of the underlying Euclidean space . ${\displaystyle \bigcup {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle V}$

Side point and middle point

A point is a Seitpunkt of when in a real page (with is included). Otherwise it is called the middle point of . ${\displaystyle x\in \Delta }$ ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})}$ ${\displaystyle x}$ ${\displaystyle \Delta ({x_{i_{0}},\,\ldots ,\,x_{i_{r}}})\subset \Delta }$ ${\displaystyle \{x_{i_{0}},\,\ldots ,\,x_{i_{r}}\}\subset \{x_{0},\,\ldots ,\,x_{n}\}}$ ${\displaystyle \Delta }$

${\displaystyle x\in \Delta }$ is therefore a mean point of ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})}$ then and only if its barycentric coordinates formed with respect to the corner points are all larger . Accordingly, is a lateral point of if and only if one of its barycentric coordinates formed is the same . ${\displaystyle x_{0},\,\ldots ,\,x_{n}}$ ${\displaystyle 0}$ ${\displaystyle x\in \Delta }$ ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})}$ ${\displaystyle x_{0},\,\ldots ,\,x_{n}}$ ${\displaystyle 0}$

Carrier simplex

For a point there is always exactly one side of which there is a central point . It is the smallest dimensioned page among all the pages that contain. This is called the carrier simplex of (in ). ${\displaystyle x\in \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})}$ ${\displaystyle {\Delta }_{x}\subseteq \Delta }$ ${\displaystyle x}$ ${\displaystyle {\Delta }_{x}}$ ${\displaystyle \Delta ({x_{i_{0}},\,\ldots ,\,x_{i_{r}}})\subseteq \Delta }$ ${\displaystyle x}$ ${\displaystyle {\Delta }_{x}}$ ${\displaystyle x\,}$ ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})}$

The index set belonging to the corners of this page is referred to below with   . ${\displaystyle {\Delta }_{x}}$ ${\displaystyle \{i_{0},\,\ldots ,\,i_{r}\}}$ ${\displaystyle I_{x}}$

Sperner's corner point numbering and complete simplexes

If an n-simplex is fixed and a (finite) simplicial complex that triangulates this simplex , and if there is also a mapping that fulfills the condition for every corner ( Sperner condition ), then one calls such a corner point numbering or Sperner's Key point numbering (English Sperner labeling ). ${\displaystyle \Delta =\Delta ({x_{0},\,\ldots ,\,x_{n}})\subset V}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle f\colon \,E\to \{0,\,\ldots ,n\}}$ ${\displaystyle f(e)\in I_{e}}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle e\in E=E({\mathcal {K}})}$ ${\displaystyle f\colon \,E\to \{0,\,\ldots ,n\}}$

For each simplex you then bet . ${\displaystyle {{\Delta }^{*}}\in {\mathcal {K}}}$ ${\displaystyle f[{{\Delta }^{*}}]=\{f(e):e\in E({{\Delta }^{*}})\}}$

It is evidently always . If it even applies , such a simplex is called complete . ${\displaystyle f[{{\Delta }^{*}}]\subseteq \{0,\,\ldots ,n\}}$ ${\displaystyle f[{{\Delta }^{*}}]=\{0,\,\ldots ,n\}}$ ${\displaystyle {{\Delta }^{*}}\in {\mathcal {K}}}$

Formulation of Sperner's lemma

The Spernersche Lemma can be formulated as follows:

The number of complete simplexes is odd for each Sperner vertex numbering. In particular, every Sperner numbering always has at least one complete simplex.

Two-dimensional example

Sperner's corner point numbering of a triangulated 2-simplex

In the figure on the right, the outermost triangle forms the 2-simplex and the smaller triangles together with their sides and corners form the triangulation . Sperner's corner point numbering can be illustrated as the coloring of the set , the values , and correspond to red , green and blue . The corners of must always be colored differently, i.e. given different values , since they are only middle points for their respective 0 sub-implications. For example, the carrier simplex of the top red corner is and its index set is accordingly . The corners of the triangulation, which lie on one of the sides of the outer triangle, may choose from the two colors of the end points of this side. The green corner in the lower right area of ​​the triangle is the only one whose carrier simplex is whole , so it can take on any of the three colors. Sperner's lemma says that in every such coloring there is an odd number of smaller triangles, the corners of which are all colored differently. In the example, these are the three with a gray background, for these simplices applies . ${\displaystyle \Delta =\Delta (x_{0},x_{1},x_{2})}$ ${\displaystyle {\mathcal {K}}}$ ${\displaystyle E({\mathcal {K}})}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 2}$ ${\displaystyle \Delta }$ ${\displaystyle f(e)}$ ${\displaystyle \Delta _{x_{0}}=\Delta (x_{0})}$ ${\displaystyle I_{x_{0}}=\{0\}}$ ${\displaystyle \Delta }$ ${\displaystyle \Delta ^{*}}$ ${\displaystyle f[\Delta ^{*}]=\{0,1,2\}}$

Application of the lemma: Lebesgue's plaster substitute

One of the most important topological theorems that can be obtained with Sperner's Lemma is Lebesgue's plaster set , which plays an essential role in dimensional theory :

There are as well a given n-simplex with vertices . For had the the vertex in opposite -dimensional side, ie the side whose vertex set of all there is. ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle \Delta \subset \mathbb {R} ^{n}}$ ${\displaystyle x_{0},\,\ldots ,\,x_{n}}$ ${\displaystyle j=0,1,\ldots ,n}$ ${\displaystyle {\Delta }_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle \Delta }$ ${\displaystyle (n-1)}$ ${\displaystyle x_{k}\neq x_{j}}$

Let there be a finite set of closed subsets of which cover . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \Delta }$

Then:

If for each there is at least one such that the intersection is the empty set , then there are always sets that have a non-empty intersection. ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle {\Delta }_{j(A)}}$ ${\displaystyle A\cap {\Delta }_{j(A)}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle n+1}$

Corollary

The Lebesgue plaster substitute has a direct consequence. It says:

For and for any n-simplex there is always one with the following property: ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle \Delta \subset \mathbb {R} ^{n}}$ ${\displaystyle \epsilon >0}$

If there is a finite set of closed subsets des that cover and each has a diameter , then there are always sets with non-empty intersections. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \Delta }$ ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle \operatorname {diam} (A)<\epsilon }$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle n+1}$

literature

items

• Bronisław Knaster , Casimir Kuratowski , Stefan Mazurkiewicz : A proof of the fixed point theorem for n-dimensional simplexes . In: Fundamenta Mathematicae . tape 14 , 1929, pp. 132-137 , doi : 10.4064 / fm-14-1-132-137 .
• Emanuel Sperner: New proof for the invariance of the dimensional number and the area . In: Treatises from the Mathematical Seminar of the Hamburg University . tape 6 , 1928, pp. 265-272 , doi : 10.1007 / BF02940617 .
• Francis Edward Su: Rental Harmony: Sperner's Lemma in Fair Division . In: The American Mathematical Monthly . tape 106 , no. 10 , 1999, p. 930-942 , doi : 10.2307 / 2589747 .

Monographs

• Wolfgang Franz : Topology I: General Topology (=  Göschen Collection . Volume 1181 ). 3. Edition. Walter de Gruyter & Co., Berlin 1968, p. 132-135 ( MR0264578 ).
• Egbert Harzheim : Introduction to combinatorial topology . Scientific Book Society, Darmstadt 1978, ISBN 3-534-07016-X .
• Michael Henle: A Combinatorial Introduction to Topology . Revised edition. Dover Publications, New York 1994, ISBN 0-486-67966-7 (first edition 1979).
• Erich Ossa: Topology. A clear introduction to the geometric and algebraic basics . 2nd, revised edition. Vieweg + Teubner, Wiesbaden 2009, ISBN 978-3-8348-0874-5 .
• Willi Rinow : Textbook of Topology (=  university books for mathematics . Volume 79 ). German Science Publishers, Berlin 1975.
• Michael J. Todd : The computation of fixed points and applications (=  Lecture notes in economics and mathematical systems . Volume 124 ). Springer, Berlin et al. 1976, ISBN 3-540-07685-9 .

Web links

• Video: The Sperner's Lemma . Institute for Scientific Film (IWF) 1983, made available by the Technical Information Library (TIB), doi : 10.3203 / IWF / D-1504 .

Individual evidence

1. ^ Henle: A Combinatorial Introduction to Topology. 1994, p. 36 ff.
2. ↑ ^{a b} Sperner: New proof for the invariance of the dimensional number and the area . In: Treatises from the Mathematical Seminar of the Hamburg University . tape 6 , 1928, pp. 265 ff .
3. ↑ Knaster, Kuratowski, Mazurkiewicz: A proof of the fixed point theorem for n-dimensional simplexes . In: Fundamenta Mathematicae . tape 14 , 1929, pp. 132 ff .
4. ↑ Represented in Aigner, Ziegler, The Book of Proofs , Chapter 25.
5. ^ Todd: The computation of fixed points and applications. 1976, p. 1 ff.
6. ^ Su: Rental Harmony: Sperner's Lemma in Fair Division . In: The American Mathematical Monthly . tape 106 , 1999, pp. 930 ff .
7. ↑ Harzheim: Introduction to combinatorial topology. 1978, p. 56 ff.
8. ↑ Rinow: Textbook of Topology. 1975, p. 341 ff.
9. ^ Franz: Topologie I. 1968, p. 132 ff.
10. ↑ Harzheim: Introduction to combinatorial topology. 1978, p. 26 ff.
11. ↑ Ossa: Topology. 2009, p. 7 ff.
12. ↑ Rinow: Textbook of Topology. 1975, p. 298 ff.
13. ↑ Harzheim: Introduction to combinatorial topology. 1978, p. 29.
14. ↑ Harzheim: Introduction to combinatorial topology. 1978, p. 33 ff.
15. ↑ In most sources, cf. Harzheim: Introduction to combinatorial topology. 1978, p. 34, the finiteness of the complex is fundamentally assumed.
16. ↑ Harzheim: Introduction to combinatorial topology. 1978, p. 37.
17. ↑ Harzheim: Introduction to combinatorial topology. 1978, p. 30.
18. ↑ ^{a b} Harzheim: Introduction to combinatorial topology. 1978, p. 37.
19. ^ Henle: A Combinatorial Introduction to Topology. 1994, p. 38.
20. ↑ ^{a b} Harzheim: Introduction to combinatorial topology. 1978, p. 57.
21. ↑ ^{a b} Harzheim: Introduction to combinatorial topology. 1978, p. 64.