Zum Inhalt springen

Lemma von Sperner

aus Wikipedia, der freien Enzyklopädie

Das Lemma von Sperner (oder auch spernersches Lemma), {{#invoke:Vorlage:lang|full|CODE=en|SCRIPTING=Latn|SERVICE=englisch}}<ref>Henle: A Combinatorial Introduction to Topology. 1994, S. 36 ff.</ref>, {{#invoke:Vorlage:lang|full|CODE=fr|SCRIPTING=Latn|SERVICE=französisch}}, ist ein mathematischer Lehrsatz aus dem Teilgebiet der Topologie. Es geht zurück auf den Mathematiker Emanuel Sperner, der es im Jahr 1928 veröffentlicht hat.<ref name="Hamburg.265ff" /> Die Bedeutung des Lemmas liegt darin, dass mit seiner Hilfe – und damit lediglich mittels elementarer kombinatorischer Methoden – eine ganze Anzahl wichtiger mathematischer Lehrsätze hergeleitet werden können. Dazu gehören vor allem der brouwersche Fixpunktsatz<ref name="Fund. Math.14" /><ref>Dargestellt in Aigner, Ziegler, Das Buch der Beweise, Kapitel 25.</ref> und verwandte Resultate<ref>Todd: The computation of fixed points and applications. 1976, S. 1 ff.</ref><ref name="Su" /> oder auch der Satz von der Invarianz der offenen Menge<ref name="Hamburg.265ff" /> und nicht zuletzt der Pflastersatz von Lebesgue.<ref>Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 56 ff.</ref><ref>Rinow: Lehrbuch der Topologie. 1975, S. 341 ff.</ref><ref>Franz: Topologie I. 1968, S. 132 ff.</ref>

Begrifflichkeit im Zusammenhang

Im Folgenden wird durchgängig ein euklidischer Raum <math>V</math> der endlichen Dimension <math>m \in \N</math> über dem Körper <math>\R</math> der reellen Zahlen zugrunde gelegt.

Simplex

Bildet man in <math>V</math> zu einem affin unabhängigen Tupel <math>(x_i)_{i=0,1, \ldots , n} \; (n \in \N , n \leq m </math>) die konvexe Hülle dieser <math>n+1</math> Punkte, so erhält man das n-Simplex <math>\Delta = \Delta ({x_0 ,\, \ldots ,\, x_n}) \subset V</math>. Die <math>x_0 ,\, \ldots ,\, x_n </math> heißen die Eckpunkte oder Ecken des zugehörigen n-Simplexes und <math>n</math> seine Dimension.<ref>Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 26 ff.</ref><ref>Ossa: Topologie. 2009, S. 7 ff.</ref><ref>Rinow: Lehrbuch der Topologie. 1975, S. 298 ff.</ref> Im Folgenden wird für die Menge <math>\{x_0 ,\, \ldots ,\, x_n \}</math> der Eckpunkte des n-Simplexes <math>\Delta </math> auch <math>E(\Delta) </math> geschrieben.

Seite eines Simplexes

Bildet man für eine Teilmenge <math>\{x_{i_0} ,\, \ldots ,\, x_{i_r} \} \subseteq \{x_0 ,\, \ldots ,\, x_n \}</math> mit <math>0 \leq i_1 < \dots < i_r \leq n</math> in gleicher Weise die konvexe Hülle, so erhält man ein Untersimplex <math>{\Delta}^* = \Delta ({x_{i_0} ,\, \ldots ,\, x_{i_r} }) \subseteq \Delta</math>, welches man als (r-dimensionale) Seite von <math>\Delta </math> bezeichnet.<ref>Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 29.</ref>

Simplizialer Komplex und Eckenmenge

Ein (endlicher) simplizialer Komplex<ref>Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 33 ff.</ref><ref>In den meisten Quellen, vgl. etwa Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 34, wird die Endlichkeit des Komplexes grundsätzlich vorausgesetzt.</ref> in dem euklidischen Raum <math>V</math> ist eine Familie <math>\mathcal{K}</math> von Simplexen von <math>\mathcal {V}</math> mit folgenden Eigenschaften:

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

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

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

Polyeder und Triangulation

Die Vereinigungsmenge <math>\bigcup {\mathcal{K}} </math>, gebildet über alle Simplexe eines simplizialen Komplexes <math>\mathcal{K} </math>, nennt man das zu <math>\mathcal{K} </math> gehörige Polyeder und <math>\mathcal{K} </math> seine Triangulation. Man sagt dann, das Polyeder werde durch <math>\mathcal{K} </math> trianguliert. Da hier vorausgesetzt ist, dass <math>\mathcal{K} </math> eine endliche Familie ist, handelt es sich bei einem solchen Polyeder stets um eine kompakte Teilmenge des zugrundeliegenden euklidischen Raumes <math> V</math>.<ref>Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 37.</ref>

Seitpunkt und mittlerer Punkt

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

<math> x \in \Delta </math> ist also ein mittlerer Punkt von <math>\Delta = \Delta ({x_0 ,\, \ldots ,\, x_n})</math> dann und nur dann, wenn seine bzgl. der Eckpunkte <math>x_0 ,\, \ldots ,\, x_n </math> gebildeten baryzentrischen Koordinaten alle größer <math> 0 </math> sind. Dementsprechend ist <math> x \in \Delta </math> ist genau dann ein Seitpunkt von <math>\Delta = \Delta ({x_0 ,\, \ldots ,\, x_n})</math>, wenn eine seiner bzgl. <math>x_0 ,\, \ldots ,\, x_n </math> gebildeten baryzentrischen Koordinaten gleich <math> 0 </math> ist.<ref>Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 30.</ref>

Trägersimplex

Für einen Punkt <math>x \in \Delta = \Delta ({x_0 ,\, \ldots ,\, x_n}) </math> existiert stets exakt eine Seite <math>{\Delta}_x \subseteq \Delta</math>, von welcher <math>x </math> ein mittlerer Punkt ist. Es ist <math>{\Delta}_x </math> die Seite kleinster Dimension unter all den Seiten <math> \Delta ({x_{i_0} ,\, \ldots ,\, x_{i_r} }) \subseteq \Delta </math>, in denen <math>x </math> enthalten ist. Dieses <math>{\Delta}_x </math> nennt man kurz das Trägersimplex von <math>x \, </math> (in <math> \Delta = \Delta ({x_0 ,\, \ldots ,\, x_n}) </math>).<ref name="Harzheim.37">Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 37.</ref>

Die zu den Ecken dieser Seite <math>{\Delta}_x </math> gehörige Indexmenge <math>\{i_0 ,\, \ldots ,\, i_r\}</math> wird im Folgenden mit <math>I_x </math> bezeichnet.

Spernersche Eckpunktbezifferung und komplette Simplexe

Ist ein n-Simplex <math>\Delta = \Delta ({x_0 ,\, \ldots ,\, x_n}) \subset V </math> fest gegeben und dazu ein (endlicher) simplizialer Komplex <math>\mathcal{K} </math> , welcher dieses Simplex trianguliert, und ist weiter <math>f\colon\, E \to \{ 0 ,\, \ldots , n \} </math> eine Abbildung, welche die Bedingung <math> f(e) \in I_e </math> für jede <math>\mathcal{K} </math>-Ecke <math> e \in E = E(\mathcal{K}) </math> erfüllt (Sperner-Bedingung), so bezeichnet man ein solches <math>f\colon\, E \to \{ 0 ,\, \ldots , n \} </math> als Eckpunktbezifferung<ref name="Harzheim.37" /> oder spernersche Eckpunktbezifferung (engl. Sperner labelling<ref>Henle: A Combinatorial Introduction to Topology. 1994, S. 38.</ref>).

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

Es ist offenbar stets <math> f[{{\Delta}^*}] \subseteq \{ 0 ,\, \ldots , n \} </math>. Gilt sogar <math> f[{{\Delta}^*}] = \{ 0 ,\, \ldots , n \} </math>, so bezeichnet man ein solches Simplex <math> {{\Delta}^*} \in \mathcal{K}</math> als komplett.<ref name="Harzheim.57">Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 57.</ref>

Formulierung des Spernerschen Lemmas

Das Spernersche Lemma kann man formulieren wie folgt:<ref name="Harzheim.57" />

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

Zweidimensionales Beispiel

Datei:Sperner2d.svg
Spernersche Eckpunktbezifferung eines triangulierten 2-Simplex

In der Abbildung rechts bildet das äußerste Dreieck den 2-Simplex <math>\Delta = \Delta(x_0, x_1, x_2)</math> und die kleineren Dreiecke zusammen mit ihren Seiten und Ecken die Triangulation <math>\mathcal K</math>. Die spernersche Eckpunktbezifferung lässt sich als Färbung der Menge <math>E(\mathcal K)</math> veranschaulichen, die Werte <math>0</math>, <math>1</math> und <math>2</math> entsprechen dabei rot, grün und blau. Die Ecken von <math>\Delta</math> müssen stets unterschiedlich gefärbt sein, also unterschiedliche Werte <math>f(e)</math> erhalten, da sie nur für ihre jeweiligen 0-Untersimplizies mittlere Punkte sind. Das Trägersimplex der obersten roten Ecke ist beispielsweise <math>\Delta_{x_0} = \Delta(x_0)</math> und ihre Indexmenge ist entsprechend <math>I_{x_0} = \{0\}</math>. 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 <math>\Delta</math> 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 <math>\Delta^*</math> gilt <math>f[\Delta^*] = \{0,1,2\}</math>.

Anwendung des Lemmas: Der Pflastersatz von Lebesgue

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:<ref name="EH-01">Harzheim: Einführung in die kombinatorische Topologie. 1978, S. 64.</ref>

Es seien <math>n \in \N</math> sowie <math>\Delta \subset \R^n</math> ein gegebenes n-Simplex mit den Eckpunkten <math>x_0 ,\, \ldots ,\, x_n</math>. Für <math>j=0,1, \ldots , n</math> sei <math>{\Delta }_j</math> die dem Eckpunkt <math>x_j</math> in <math>\Delta</math> gegenüberliegende <math>(n-1)</math>-dimensionale Seite, also diejenige Seite, deren Eckenmenge aus allen <math>x_k \neq x_j</math> besteht.
Weiter sei eine endliche Menge <math>\mathcal {A}</math> von abgeschlossenen Teilmengen des <math>\R^n</math> gegeben, welche <math>\Delta</math> überdecken.
Dann gilt:
Gibt es zu jedem <math>A \in \mathcal {A}</math> mindestens ein <math>{\Delta }_{j(A)}</math> derart, dass die Schnittmenge <math>A \cap {\Delta }_{j(A)}</math> die leere Menge ist, so gibt es in <math>\mathcal {A}</math> stets <math>n+1</math> Mengen, die eine nichtleere Schnittmenge haben.

Korollar

Der Lebesgue’sche Pflastersatz zieht eine direkte Folgerung nach sich. Sie besagt:<ref name="EH-01" />

Für <math>n \in \N</math> und für jedes beliebige n-Simplex <math>\Delta \subset \R^n</math> gibt es stets ein <math>\epsilon > 0</math> mit folgender Eigenschaft:
Ist <math>\mathcal {A}</math> eine endliche Menge abgeschlossener Teilmengen des <math>\R^n</math>, die <math>\Delta</math> überdecken, und hat jedes <math>A \in \mathcal {A}</math> einen Durchmesser <math>\operatorname{diam}(A) < \epsilon</math>, so gibt es in <math>\mathcal {A}</math> stets <math>n+1</math> Mengen mit nichtleerer Schnittmenge.

Verwandter Artikel

Literatur

Artikel

  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}

Monographien

  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}
  • {{#invoke:Vorlage:Literatur|f}}

Weblinks

Einzelnachweise

<references> <ref name="Fund. Math.14"> {{#invoke:Vorlage:Literatur|f}} </ref> <ref name="Hamburg.265ff"> {{#invoke:Vorlage:Literatur|f}} </ref> <ref name="Su"> {{#invoke:Vorlage:Literatur|f}} </ref> </references>

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Lemma_von_Sperner&oldid=2707890“