Lemma von Sperner

mathematischer Satz

Das Lemma von Sperner, oft Spernersches Lemma genannt, englisch Sperner’s Lemma[1], 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.[2] Die Bedeutung des Lemmas liegt darin, dass mit seiner Hilfe – und damit lediglich mittels elementarer kombinatorischer Methoden – eine ganze Anzahl wichtiger mathematischer Lehrsätze zu beweisen sind, wie der brouwersche Fixpunktsatz[3][4] und verwandte Resultate[5][6] oder auch der Satz von der Invarianz der offenen Menge[2] und nicht zuletzt der Pflastersatz von Lebesgue.[7][8][9]

Begrifflichkeit im Zusammenhang Bearbeiten

Im Folgenden wird durchgängig ein euklidischer Raum   der endlichen Dimension   über dem Körper   der reellen Zahlen zugrunde gelegt.

Simplex Bearbeiten

Bildet man in   zu gegebenen   affin unabhängigen Punkten   ( ) die konvexe Hülle dieser Punkte, so erhält man das n-Simplex  . Die   heißen die Eckpunkte oder Ecken des zugehörigen n-Simplexes und   seine Dimension.[10][11][12] Im Folgenden wird für die Menge   der Eckpunkte des n-Simplexes   auch   geschrieben.

Seite eines Simplexes Bearbeiten

Bildet man für eine Teilmenge   mit   in gleicher Weise die konvexe Hülle, so erhält man ein Untersimplex  , welches man als (r-dimensionale) Seite von   bezeichnet.[13]

Simplizialer Komplex und Eckenmenge Bearbeiten

Ein (endlicher) simplizialer Komplex[14][15] in dem euklidischen Raum   ist eine Familie   von Simplexen von   mit folgenden Eigenschaften:

  1. Mit jedem Simplex   gehört auch jede Seite von   zu  .
  2. Der Schnitt   zweier Simplexe von   ist leer oder gemeinsame Seite beider Simplexe  .
  3.   ist eine endliche Menge.

Die Familie der Seiten eines n-Simplexes   bildet stets einen endlichen simplizialen Komplex.

Bildet man die Vereinigungsmenge  , so erhält man die Eckenmenge von  , nämlich die Menge aller Eckpunkte der in   vorkommenden Simplexe.

Polyeder und Triangulation Bearbeiten

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

Seitpunkt und mittlerer Punkt Bearbeiten

Ein Punkt   heißt ein Seitpunkt von  , wenn   in einer echten Seite   (mit  ) enthalten ist. Andernfalls wird er als mittlerer Punkt von   bezeichnet.

  ist also ein mittlerer Punkt von   dann und nur dann, wenn seine bzgl. der Eckpunkte   gebildeten baryzentrischen Koordinaten alle größer   sind. Dementsprechend ist   ist genau dann ein Seitpunkt von  , wenn eine seiner bzgl.   gebildeten baryzentrischen Koordinaten gleich   ist.[17]

Trägersimplex Bearbeiten

Für einen Punkt   existiert stets exakt eine Seite   , von welcher   ein mittlerer Punkt ist. Es ist   die Seite kleinster Dimension unter all den Seiten   , in denen   enthalten ist. Dieses   nennt man kurz das Trägersimplex von   (in  ).[18]

Die zu den Ecken dieser Seite   gehörige Indexmenge   wird im Folgenden mit   bezeichnet.

Spernersche Eckpunktbezifferung und komplette Simplexe Bearbeiten

Ist ein n-Simplex   fest vorgegeben und dazu ein (endlicher) simplizialer Komplex   , welcher dieses Simplex trianguliert, und ist weiter   eine Abbildung, welche die Bedingung   für jede  -Ecke   erfüllt (Sperner-Bedingung), so bezeichnet man ein solches   als Eckpunktbezifferung[18] oder Spernersche Eckpunktbezifferung (engl. Sperner labelling[19]).

Für jedes Simplex   setzt man dann  .

Es ist offenbar stets  . Gilt sogar  , so bezeichnet man ein solches Simplex   als komplett.[20]

Formulierung des Spernerschen Lemmas Bearbeiten

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

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

Zweidimensionales Beispiel Bearbeiten

 
Spernersche Eckpunktbezifferung eines triangulierten 2-Simplex

In der Abbildung rechts bildet das äußerste Dreieck den 2-Simplex   und die kleineren Dreiecke zusammen mit ihren Seiten und Ecken die Triangulation  . Die Spernersche Eckpunktbezifferung lässt sich als Färbung der Menge   veranschaulichen, die Werte  ,   und   entsprechen dabei rot, grün und blau. Die Ecken von   müssen stets unterschiedlich gefärbt sein, also unterschiedliche Werte   erhalten, da sie nur für ihre jeweiligen 0-Untersimplizies mittlere Punkte sind. Der Trägersimplex der obersten roten Ecke ist beispielsweise   und ihre Indexmenge ist entsprechend  . Die Ecken der Triangulation, die auf einer der Seiten des äußerem Dreiecks liegen, dürfen jeweils aus den beiden Farben der Endpunkte dieser Seite wählen. Die grüne Ecke im unteren rechten Bereich des Dreiecks ist die einzige, deren Trägersimplex ganz   ist, sie kann also eine beliebige der drei Farben annehmen. Das Spernersche Lemma besagt nun, dass es in jeder solchen Färbung eine ungerade Anzahl von kleineren Dreiecken gibt, deren Eckpunkte alle unterschiedlich gefärbt sind. Im Beispiel sind das die drei grau hinterlegten, für diese Simplizes   gilt  .

Anwendung des Lemmas: Der Pflastersatz von Lebesgue Bearbeiten

Zu den bedeutenden topologischen Sätzen, welche mit dem Spernerschen Lemma zu gewinnen sind, zählt als einer der wichtigsten der Pflastersatz von Lebesgue, der eine wesentliche Rolle in der Dimensionstheorie spielt:[21]

Es seien   sowie   ein gegebenes n-Simplex mit den Eckpunkten  . Für   sei   die dem Eckpunkt   in   gegenüberliegende  -dimensionale Seite, also diejenige Seite, deren Eckenmenge aus allen   besteht.
Weiter sei eine endliche Menge   von abgeschlossenen Teilmengen des   gegeben, welche   überdecken.
Dann gilt:
Gibt es zu jedem   mindestens ein   derart, dass die Schnittmenge   die leere Menge ist, so gibt es in   stets   Mengen, die eine nichtleere Schnittmenge haben.

Korollar Bearbeiten

Der Lebesgue’sche Pflastersatz zieht eine direkte Folgerung nach sich. Sie besagt:[21]

Für   und für jedes beliebige n-Simplex   gibt es stets ein   mit folgender Eigenschaft:
Ist   eine endliche Menge abgeschlossener Teilmengen des  , die   überdecken, und hat jedes   einen Durchmesser  , so gibt es in   stets   Mengen mit nichtleerer Schnittmenge.

Literatur Bearbeiten

Artikel

Monographien

  • Wolfgang Franz: Topologie I: Allgemeine Topologie (= Sammlung Göschen. Band 1181). 3. Auflage. Walter de Gruyter & Co., Berlin 1968, S. 132–135 (MR0264578).
  • 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 (Erstausgabe: 1979).
  • Erich Ossa: Topologie. Eine anschauliche Einführung in die geometrischen und algebraischen Grundlagen. 2., überarbeitete Auflage. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0874-5.
  • Willi Rinow: Lehrbuch der Topologie (= Hochschulbücher für Mathematik. Band 79). Deutscher Verlag der Wissenschaften, Berlin 1975.
  • Michael J. Todd: The computation of fixed points and applications (= Lecture notes in economics and mathematical systems. Band 124). Springer, Berlin u. a. 1976, ISBN 3-540-07685-9.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Henle: A Combinatorial Introduction to Topology. 1994, S. 36 ff.
  2. a b Sperner: Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. In: Abhandlungen aus dem Mathematischen Seminar der Hamburgischen Universität. Band 6, 1928, S. 265 ff.
  3. Knaster, Kuratowski, Mazurkiewicz: Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe. In: Fundamenta Mathematicae. Band 14, 1929, S. 132 ff.
  4. Dargestellt in Aigner, Ziegler, Das Buch der Beweise, Kapitel 25.
  5. Todd: The computation of fixed points and applications. 1976, S. 1 ff.
  6. Su: Rental Harmony: Sperner’s Lemma in Fair Division. In: The American Mathematical Monthly. Band 106, 1999, S. 930 ff.
  7. Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 56 ff.
  8. Rinow: Lehrbuch der Topologie. 1975, S. 341 ff.
  9. Franz: Topologie I. 1968, S. 132 ff.
  10. Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 26 ff.
  11. Ossa: Topologie. 2009, S. 7 ff.
  12. Rinow: Lehrbuch der Topologie. 1975, S. 298 ff.
  13. Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 29.
  14. Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 33 ff.
  15. In den meisten Quellen, vgl. etwa Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 34, wird die Endlichkeit des Komplexes grundsätzlich vorausgesetzt.
  16. Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 37.
  17. Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 30.
  18. a b Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 37.
  19. Henle: A Combinatorial Introduction to Topology. 1994, S. 38.
  20. a b Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 57.
  21. a b Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 64.