Lemma von Sperner

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Lemma von Sperner, oft Spernersches Lemma[1] genannt (englisch Sperner’s Lemma[2]), ist ein mathematisches Resultat aus dem Teilgebiet der Topologie. Es geht zurück auf den deutschen Mathematiker Emanuel Sperner, der es im Jahr 1928 veröffentlicht hat.[3] Die Bedeutung des Lemmas liegt darin, dass es sich als fundamentales Hilfsmittel erwiesen hat, um mit elementaren kombinatorischen Methoden eine ganze Anzahl bedeutender mathematischer Lehrsätze zu beweisen, wie den brouwerschen Fixpunktsatz[4] und verwandte Resultate[5][6] oder auch den Satz von der Invarianz der offenen Menge[3] oder den Pflastersatz von Lebesgue.[7][8]

Begrifflichkeit im Zusammenhang[Bearbeiten]

Im Folgenden wird durchgängig ein euklidischer Raum V der endlichen Dimension m \in \N über dem Körper \R der reellen Zahlen zugrundegelegt.

Simplex[Bearbeiten]

Bildet man in V zu gegebenen n+1 affin unabhängigen Punkten x_0 ,\, \ldots ,\,  x_n ( n \in \N ,  n \leq m ) die konvexe Hülle dieser Punkte, so erhält man das n-Simplex \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}) \subset V. Die x_0 ,\, \ldots ,\,  x_n heißen die Eckpunkte oder Ecken des zugehörigen n-Simplexes und n seine Dimension.[9][10][11] Im Folgenden wird für die Menge \{x_0 ,\, \ldots ,\,  x_n \} der Eckpunkte des n-Simplexes \Delta auch E(\Delta) geschrieben.

Seite eines Simplex[Bearbeiten]

Bildet man für eine Teilmenge \{x_{i_0} ,\, \ldots ,\,  x_{i_r} \}  \subseteq  \{x_0 ,\, \ldots ,\,  x_n \} mit 0 \leq i_1 < \dots  < i_r \leq  n in gleicher Weise die konvexe Hülle, so erhält man ein Untersimplex {\Delta}^* = \Delta ({x_{i_0} ,\, \ldots ,\,  x_{i_r} })  \subseteq  \Delta, welches man als (r-dimensionale) Seite von \Delta bezeichnet.[12]

Simplizialer Komplex und Eckenmenge[Bearbeiten]

Ein (endlicher) simplizialer Komplex[13][14] in dem euklidischen Raum V ist eine Familie \mathcal{K} von Simplizes von \mathcal {V} mit folgenden Eigenschaften:

  1. Mit jedem Simplex {{\Delta}^*} \in \mathcal{K} gehört auch jede Seite von {{\Delta}^*} zu \mathcal{K}.
  2. Der Schnitt {{\Delta}^*}_1 \cap {{\Delta}^*}_2 zweier Simplizes von  {{\Delta}^*}_1 ,\, {{\Delta}^*}_2  \in  \mathcal{K} ist leer oder gemeinsame Seite beider Simplizes  {{\Delta}^*}_1 ,\, {{\Delta}^*}_2 .
  3. \mathcal{K} ist eine endliche Menge.

Die Familie der Seiten eines n-Simplexes \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}) \subset V bildet stets einen endlichen simplizialen Komplex.

Bildet man die Vereinigungsmenge   E = E(\mathcal{K}) = \bigcup_{ {{\Delta}^*} \in \mathcal{K} } E({\Delta}^*) , so erhält man die Eckenmenge von \mathcal{K}, nämlich die Menge aller Eckpunkte der in \mathcal{K} vorkommenden Simplizes.

Polyeder und Triangulation[Bearbeiten]

Die Vereinigungsmenge \bigcup {\mathcal{K}} , gebildet über alle Simplizes eines simplizialen Komplexes \mathcal{K} , nennt man das zu \mathcal{K} gehörige Polyeder und \mathcal{K} seine Triangulation. Man sagt dann, das Polyeder werde durch \mathcal{K} trianguliert. Da hier vorausgesetzt ist, dass \mathcal{K} eine endliche Familie ist, handelt es sich bei einem solchen Polyeder stets um eine kompakte Teilmenge des zugrundeliegenden euklidischen Raumes  V.[15]

Seitpunkt und mittlerer Punkt[Bearbeiten]

Ein Punkt  x \in \Delta heißt ein Seitpunkt von \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}), wenn  x in einer echten Seite  \Delta ({x_{i_0} ,\, \ldots ,\,  x_{i_r} })  \subset  \Delta ( mit \{x_{i_0} ,\, \ldots ,\,  x_{i_r} \}  \subset  \{x_0 ,\, \ldots ,\,  x_n \} ) enthalten ist. Andernfalls wird er als mittlerer Punkt von \Delta bezeichnet.

 x \in \Delta ist also ein mittlerer Punkt von \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}) dann und nur dann, wenn seine bzgl. der Eckpunkte x_0 ,\, \ldots ,\,  x_n gebildeten baryzentrischen Koordinaten alle größer  0 sind. Dementsprechend ist  x \in \Delta ist genau dann ein Seitpunkt von \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}), wenn eine seiner bzgl. x_0 ,\, \ldots ,\,  x_n gebildeten baryzentrischen Koordinaten gleich  0 ist.[16]

Trägersimplex[Bearbeiten]

Für einen Punkt x \in  \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}) existiert stets exakt eine Seite {\Delta}_x  \subseteq  \Delta , von welcher x  ein mittlerer Punkt ist. Es ist {\Delta}_x die Seite kleinster Dimension unter all den Seiten  \Delta ({x_{i_0} ,\, \ldots ,\,  x_{i_r} })  \subseteq \Delta  , in denen x enthalten ist. Dieses {\Delta}_x  nennt man kurz das Trägersimplex von x \, (in  \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}) ).[17]

Die zu den Ecken dieser Seite {\Delta}_x  gehörige Indexmenge wird im Folgenden mit   I_x   bezeichnet.

Spernersche Eckpunktbezifferung und komplette Simplizes[Bearbeiten]

Ist ein n-Simplex \Delta = \Delta ({x_0 ,\, \ldots ,\,  x_n}) \subset  V fest vorgegeben und dazu ein (endlicher) simplizialer Komplex \mathcal{K} , welcher dieses Simplex trianguliert, und ist weiter f\colon\, E \to \{ 0 ,\,  \ldots , n \} eine Abbildung, welche die Bedingung  f(e) \in I_e  für jede \mathcal{K} -Ecke  e \in E  = E(\mathcal{K}) erfüllt (Sperner-Bedingung), so bezeichnet man ein solches f\colon\, E \to \{ 0 ,\,  \ldots , n \} als Eckpunktbezifferung[17] oder Spernersche Eckpunktbezifferung (engl. Sperner labelling[18]).

Für jedes Simplex {{\Delta}^*} \in \mathcal{K} setzt man dann  f[{{\Delta}^*}] = \{f(e): e  \in E({{\Delta}^*})  \} .

Es ist offenbar stets  f[{{\Delta}^*}]  \subseteq \{ 0 ,\,  \ldots , n \} . Gilt sogar  f[{{\Delta}^*}] =  \{ 0 ,\,  \ldots , n \} , so bezeichnet man ein solches Simplex  {{\Delta}^*} \in \mathcal{K} als komplett.[19]

Formulierung des Spernerschen Lemmas[Bearbeiten]

Das Spernersche Lemma kann man formulieren wie folgt:[19]

Für jede Spernersche Eckpunktbezifferung ist die Anzahl der kompletten Simplizes ungerade. Insbesondere hat jede Spernersche Eckpunktbezifferung stets mindestens ein komplettes Simplex.

Literatur[Bearbeiten]

Artikel[Bearbeiten]

  • B. Knaster, K. Kuratowski, S. Mazurkiewicz: Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe. In: Fund. Math. 14, 1929, S. 132-137.
  • Emanuel Sperner: Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. In: Abh. Math. Sem. Univ. Hamburg. 6, 1928, S. 265–272.
  • Francis Edward Su: Rental Harmony: Sperner’s Lemma in Fair Division. In: Amer. Math. Monthly. 106, 1999, S. 930-942.

Monographien[Bearbeiten]

  •  Egbert Harzheim: Einführung in die kombinatorische Topologie. Wissenschaftliche Buchgesellschaft, Darmstadt 1978, ISBN 3-534-07016-X.
  •  Michael Henle: A Combinatorial Introduction to Topology. überarbeitete Auflage. Dover Publications, New York 1994, ISBN 0-486-67966-7 (Originalveröffentlichung: 1979).
  •  Erich Ossa: Topologie. Eine anschauliche Einführung in die geometrischen und algebraischen Grundlagen. 2. Auflage. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0874-5.
  •  Willi Rinow: Lehrbuch der Topologie. Deutscher Verlag der Wissenschaften, Berlin 1975.
  •  Michael J. Todd: The computation of fixed points and applications (Lecture notes in economics and mathematical systems 124). Springer, Berlin 1976, ISBN 3-540-07685-9.

Einzelnachweise[Bearbeiten]

  1. Harzheim, S. 56 ff.
  2. Henle, S. 36 ff.
  3. a b  Sperner: Abh. Math. Sem. Hamburg. Nr. 6, S. 265 ff.
  4.  Knaster, Kuratowski, Mazurkiewicz: In: Fund. Math.. Nr. 14, S. 132 ff.
  5. Todd, S. 1 ff.
  6.  Su: In: Amer. Math. Monthly. Nr. 106, S. 930 ff.
  7. Harzheim, S. 64 ff.
  8. Rinow, S. 341 ff.
  9. Harzheim, S. 26 ff
  10. Ossa, S. 7 ff.
  11. Rinow, S. 298 ff.
  12. Harzheim, S. 29
  13. Harzheim, S. 33 ff
  14. In den meisten Quellen, vgl. etwa Harzheim, S. 34, wird die Endlichkeit des Komplexes grundsätzlich vorausgesetzt.
  15. Harzheim, S. 37
  16. Harzheim, S. 30
  17. a b Harzheim, S. 37
  18. Henle, S. 38
  19. a b Harzheim, S. 57