Benutzer:Thorsten 1996/Sperners Lemma

In der Mathematik ist das Sperner-Lemma eine kombinatorische Analogie des Brouwer Fixpunktsatzes, der sich aus ihm ergibt. Das Sperner-Lemma sagt, dass jede Sperner-Färbung (unten beschrieben) einer Triangulation eines n-dimensionalen Simplex eine Zelle mit allen Farben beinhaltet. Das erste Ergebnis dieser Art bewies Emanuel Sperner im Zusammenhang mit dem Jordan-Brouwer-Zerlegungssatz. Sperner-Färbungen wurden für die effektive Berechnung von Fixpunkten, für Wurzelziehungsalgorithmen und für Algorithmen für gerechte Aufteilung angewendet.

Eindimensionaler Fall

In einer Dimension kann Sperners Lemma als untergeordnete Version des Zwischenwertsatzes betrachtet werden. Dieser Fall besagt im Wesentlichen, dass, wenn eine diskrete Funktion mit den Werten 0 und 1, beginnend mit 0 und endend mit 1, die Werte wechselt, die Anzahl der Wechsel ungerade ist.

Zweidimensionaler Fall

Datei:Sperner-Färbung.jpg

System der Sperner-Färbung

Der zweidimensionale Fall ist der am häufigsten vorkommende. Er wird wie folgt angegeben:

Es ist ein Dreieck ABC und eine Triangulation dessen gegeben. Die Menge M der Ecken von T ist mit drei Farben so gefärbt, dass

• A, B und C jeweils grün, blau und rot gefärbt sind.
• jede Kreuzung an einer Außenkante von ABC nur mit einer der Farben an den Enden dieser Kante gefärbt ist. Zum Beispiel muss jede Kreuzung auf AC entweder mit Grün oder Rot gefärbt sein.

Unter diesen Bedingungen existiert ein Dreieck von T, dessen Eckpunkte in den drei Farben und auch in der Reihenfolge der Eckpunkte gefärbt sind, in diesem Fall das Dreieck 2B3. Meistens gibt es eine ungerade Anzahl solcher Dreiecke.

Mehrdimensionaler Fall

Im allgemeinen bezieht sich der Begriff auf einen n-dimensionalen Simplex

${\mathcal {A}}=A_{1}A_{2}\ldots A_{n+1}.$

Wir betrachten eine Triangulation T von ABC, das ist eine seperate Aufteilung der ${\mathcal {A}}$ in kleinere, n-dimensionale Simplexe. Wir nennen die Färbungsfunktion f : M → {1,2,3,...,n,n+1}, wobei M wieder die Menge der Ecken von T ist. Die Regeln der Färbung sind:

1. Die Ecken des großen Simplex sind mit unterschiedlichen Farben gefärbt, d.h. f(A_i) = i for 1 ≤ i ≤ n+1.
2. Die Ecken von T auf einer bestimmten k-dimensionalen Unterseite $A_{i_{1}}A_{i_{2}}\ldots A_{i_{k}}$ sind nur mit den Farben $f(A_{i_{1}}),f(A_{i_{2}}),\ldots ,f(A_{i_{k}})$ gefärbt.

Dann gibt es eine ungerade Anzahl von Simplizes von T, deren Ecken in allen n+1 Farben sind. Von diesen Simplizies muss es mindestens eine geben.

Beweis

Wir werden uns zuerst an den zweidimensionalen Fall richten. Betrachten Sie einen Graphen G, gebildet aus der Triangulation T wie folgt:

Die Eckpunkte von G bestehen aus einem Teil von T plus dem Gebiet außerhalb des Dreiecks. Zwei Eckpunkte werden mit einem Rand angeschlossen, wenn sich ihre entsprechenden Gebiete teilen, färbte sich eine gemeinsame Grenze mit einem Endpunkt 1 und die anderen farbigen 2.

Bemerken Sie, dass auf dem Zwischenraum AB dort eine ungerade Zahl von Grenzen gefärbt 1-2 ist (einfach, weil A 1 gefärbt wird, wird B 2 gefärbt; und weil wir AB vorankommen, muss es eine ungerade Zahl von Farbwechseln geben, um verschiedene Farben am Anfang und am Ende zu bekommen). Deshalb hat der Scheitelpunkt von G entsprechend dem Außengebiet einen sonderbaren Grad. Aber es ist (das Quittungslemma) dass in einem begrenzten Graphen bekannt es gibt eine gerade Zahl von Scheitelpunkten mit dem sonderbaren Grad. Deshalb hat der restliche Graph, des Außengebiets ausschließend, eine ungerade Zahl von Scheitelpunkten mit dem sonderbaren Grad entsprechend Mitgliedern von T.

Es kann leicht gesehen werden, dass der einzige mögliche Grad eines Dreiecks von T 0, 1 oder 2 ist, und dass der Grad 1 einem Dreieck entspricht, das mit den drei Farben 1, 2 und 3 gefärbt ist.

So haben wir einen ein bisschen stärkeren Beschluss erhalten, der sagt, dass in einer Triangulation T es eine ungerade Zahl (und mindestens ein) von voll gefärbten Dreiecken gibt.

Ein mehrdimensionaler Fall kann durch die Induktion auf der Dimension eines Simplexes herausgestellt werden. Wir wenden dasselbe Denken, wie im 2-dimensionalen Fall an, um dass in einer n-dimensional Triangulation zu beschließen, gibt es eine ungerade Zahl von voll gefärbtem simplices. [editieren Sie] Generalisationen

Das Lemma von Sperner ist zu colorings von polytopes mit n Scheitelpunkten verallgemeinert worden.. In diesem Fall gibt es mindestens n-k völlig etikettierte simplices, wo k die Dimension des polytope ist und "völlig etikettiert" anzeigt, dass jedes Etikett auf dem Simplex eine verschiedene Farbe hat. Zum Beispiel, wenn ein Vieleck mit n Scheitelpunkten trianguliert und gemäß dem Kriterium von Sperner gefärbt wird, dann gibt es mindestens n-2 völlig etikettierte Dreiecke. Die allgemeine Behauptung wurde von Atanassov 1996 vermutet, der es für den Fall k=2 prüfte. [1] wurde Der Beweis des allgemeinen Falls zuerst von de Loera, Peterson, und Su 2002 gegeben. [2] [editieren Sie] Anwendungen

Sperner colorings sind für die wirksame Berechnung von Festkommas verwendet worden. Ein Sperner-Färben kann solch gebaut werden, der völlig simplices etikettierte, entsprechen Festkommas einer gegebenen Funktion. Indem man eine Triangulation kleiner und kleiner macht, kann man zeigen, dass die Grenze des völlig etikettierten simplices genau das Festkomma ist. Folglich stellt die Technik einen Weg zur Verfügung, Festkommas näher zu kommen.

Deshalb kann das Lemma von Sperner auch in wurzelfindenden Algorithmen und schönen Abteilungsalgorithmen verwendet werden.

E. Sperner hat die Entwicklung, den Einfluss und die Anwendungen seines kombinatorischen Lemmas [in 3] präsentiert. [editieren Sie] Sieh auch

   Brouwer Festkomma-Lehrsatz
   Borsuk-Ulam Lehrsatz
   Das Lemma des Essens
   Topologische Kombinatorik

[editieren Sie] Verweisungen

   ^ K. T. Atanassov (1996). "Auf dem Lemma von Sperner". Knopf. Sci. Mathematik. Hungarica 32: 71-74.
   ^ Jesus de Loera, Elisha Peterson, und Francis Su (2002). "Eine polytopal Generalisation des Lemmas von Sperner". Zeitschrift der Kombinatorischen Theorie-Reihe 100 (1): 1-26. doi:10.1006/jcta.2002.3274.

3. ^ E. Sperner, Fünfzig Jahre der Weiterentwicklung eines kombinatorischen Lemmas,

              Teil A, p.183-197,
              Teil B, p.199-214,
              in: Numerische Lösungen von hoch nichtlinearen Problemen, 
                  Festkomma-Algorithmen und Complementarity Probleme,
                  W. Forster (Hrsg.). Nördliches Holland, Amsterdam, 1980.

Weblinks

• Proof of Sperners Lemma bei cut-the-Knoten