Zur Relevanz des Lemmas von Sperner in Theorie und Alltag

Inhaltsverzeichnis

1 Einleitung
1.1 Wichtige Begriffe für das Verständnis des Lemmas
1.1.1 Grundbegriffe aus der Graphentheorie

2 Lemma von Sperner für
2.1 Beweis des Lemmas für

3 Lemma von Sperner für höhere Dimensionen
3.1 Konvexe Menge und konvexe Hülle
3.2 Simplex
3.3 Lemma von Sperner
3.4. Beweis des Lemmas

4 Der Brouwersche Fixpunktsatz
4.1 Beweis des Fixpunktsatzes von Brouwer

5 Das Kuchenproblem
5.1 Grundlegende Definitionen
5.2 Neidfrei-gerecht vs. Proportional-gerecht
5.3 Das Moving Knife – Verfahren
5.4 Neidfrei-gerechte Verteilung mithilfe des Lemmas von Sperner
5.4.1 Beispiel für
5.4.2 Aufteilung auf – Spieler

6 Resümee und Ausblick

Literaturverzeichnis

1 Einleitung

Im Rahmen des Seminars „Differentialtopologie“ bei Prof. Dr. Abbondandolo habe ich mich entschlossen eine Bachelorarbeit in diesem Themenfeld zu schreiben. Diese Arbeit basiert auf den Hilfssatz von Sperner, der sich als ein fundamentales Hilfsmittel erwiesen hat. Viele mathematische Lehrsätze wurden durch dieses Lemma kombinatorisch elegant bewiesen, wie zum Beispiel der Brouwersche Fixpunktsatz, der in dieser Arbeit auch vorgeführt wird.

Den Kern dieser Arbeit bilden zwei verschiedene Beweise, die mit Hilfe des Lemmas von Sperner erfolgreich bewiesen worden sind. Zum einen den Brouwerschen Fixpunktsatz und zum anderen ein alltägliches Problem.

Letzteres handelt von einem „Kuchenproblem“ (cake division problem), welches in Kapitel 6 genauer erläutert und mit Hilfe des Lemmas gelöst werden kann.

1.1 Wichtige Begriffe für das Verständnis des Lemmas

Im folgenden Kapitel befassen wir uns zunächst mit Sperners Lemma für , da für diese Dimension der Hilfssatz bildlich sehr gut darzustellen ist. Wenn wir das Prinzip des Lemmas verstanden haben, ist es relativ einfach, dieses Lemma auf höhere Dimension zusammenzufassen und dann auch zu beweisen. Bevor wir es für Dimension zwei formulieren können, benötigen wir einige mathematische Begriffe aus der Graphentheorie, die in diesem Kapitel kurz und knapp verfasst werden (Siehe auch [1, Kapitel 2.1]).

1.1.1 Grundbegriffe aus der Graphentheorie

Definition 1.1. Ein Graph ist ein Tupel , wobei eine (endliche) nichtleere Menge von Knoten ist. Die Menge E ist eine Teilmenge der zweielementigen Teilmengen von , also

Abbildung in dieser Leseprobe nicht enthalten

Die Elemente der Menge bezeichnet man als Kanten.

Definition 1.2. Der Grad (engl. degree) von bezeichnet die Anzahl der Knoten von .

Somit gilt auch folgendes Lemma:

Lemma 1.3. Für jeden Graph gilt

Abbildung in dieser Leseprobe nicht enthalten

Beweis. Wir verwenden die Regel des doppelten Abzählens. Auf der linken Seite wird jede Kante genau zweimal gezählt. Einmal, wenn betrachtet wird und zum zweiten Mal, wenn wir bei angekommen sind. Auf der rechten Seite wird jede Kante ebenfalls zweimal gezählt.

Das folgende Lemma aus der Graphentheorie wird für das Lemma von Sperner ebenso hilfreich sein:

Lemma 1.4. Für jeden Graph gilt: Die Anzahl der Knoten mit ungeraden Grad ist gerade.

Beweis. Aus Lemma 1.3 folgt, dass die Summe der Grade aller Knoten eine gerade Zahl ist. Da aber die Summe der geraden Graden gerade sein muss, lässt sich nun folgern, dass auch die Summe der ungeraden Grade gerade ist. Die Summe von ungeraden Zahlen ist genau dann gerade, wenn ihre Anzahl gerade ist. Somit muss die Anzahl von Knoten ungeraden Grades gerade sein.

Definition 1.5. Ein Pfad entsteht aus Knoten und Kanten, die aufeinander folgende Knoten miteinander verbinden.

Definition 1.6. (Triangulierung). Gegeben sei ein Dreieck . Eine Triangulierung von ist eine Unterteilung auf kleinere Dreiecke, sodass keine Ecke eines Dreiecks auf einer eines anderen Dreiecks liegt (siehe Abb. 1).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Triangulierung eines Dreiecks

Eine Triangulierung ist also ein Dreieck, das noch einmal in mehreren Dreiecken unterteilt wird.

2 Lemma von Sperner für

Lemma 2.1 (Lemma von Sperner für ) . Gegeben sei ein Dreieck und eine Triangulierung von . Außerdem sei jede Ecke der Triangulierung mit einer „Farbe“ aus der Menge markiert, sodass jeweils die Farbe erhält und für die Ecken entlang der Kante von nach nur die Farben oder benutzt werden dürfen, wobei wir im Inneren keine Einschränkungen machen, was wiederum bedeutet: Die Inneren Ecken können beliebig mit oder gefärbt werden.

Dann gilt:

Es gibt ein Dreieck der Triangulierung von , dessen Ecken alle drei Markierungen besitzen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Bildliche Darstellung des Lemmas für

In Abbildung 2 enthalten die grau markierten Dreiecke die drei verschiedenen Farben. , und entsprechen hier 1,2 und 3 (siehe auch [2]).

Wir beweisen außerdem eine stärkere Aussage, die besagt, dass die Anzahl der Dreiecke mit den drei unterschiedlich gefärbten Kanten nicht nur ungleich Null ist, sondern immer ungerade ist.

2.1 Beweis des Lemmas für

Für den folgenden Beweis orientieren wir uns an [2].

Beweis. Sei

Abbildung in dieser Leseprobe nicht enthalten

Zwei Dreiecke sind durch eine Kante verbunden, falls sie eine gemeinsame Seite besitzen, deren Ecken die Farben 1 und 2 haben. K ist durch eine Kante mit allen Dreiecken verbunden, die eine Seite auf dem Rand von T haben, deren Ecken die Farben 1 und 2 haben (diese Seiten liegen auf der Seite zwischen ). Wir erhalten dann einen Graph, der Grad 1 hat in allen Dreiecken, die 3 verschiedene Farben enthalten, Grad 2 in den Dreiecken, die die Farben 1 und 2 enthalten und Grad 0, wenn das Dreieck nicht beide Farben 1 und 2 besitzt. Daraus kann man schließen, dass nur in den Dreiecken, die die drei verschiedenen Farben enthalten, der Grad ungerade ist (Grad 1).

Nun schauen wir uns die Seiten von T mit den Ecken an (siehe Abb. 3). Entlang dieser Seite existiert eine ungerade Zahl von Wechseln zwischen den beiden Farben 1 und 2. Dies bedeutet wiederum, dass der Grad von K ungerade ist. Da die Anzahl der Knoten mit ungeradem Grad gerade ist (siehe Lemma 1.4 auf S.3) und der Grad von K ungerade ist, haben ungerade viele Dreiecke der Triangulierung einen ungeraden Grad. Wie schon bemerkt sind diese Dreiecke genau die, deren Ecken verschiedene Farben besitzen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: bildliche Darstellung des Beweis

In der Abbildung 3 bilden die gestrichelten Linien den definierten Graph.

3 Lemma von Sperner für höhere Dimensionen

Bevor wir nun das Lemma von Sperner für höhere Dimensionen aufstellen können, brauchen wir wieder einige Definitionen aus der Geometrie. Das Kapitel ist angelehnt an [3].

3.1 Konvexe Menge und konvexe Hülle

Definition 3.1. (konvexe Menge). Eine Teilmenge heißt konvexe Menge, wenn zwei beliebige Punkte eine Verbindungsstrecke bilden, die in dieser Menge liegt (siehe Abb. 4).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Bildliche Darstellung einer konvexen und nicht konvexen Menge

Bemerkung 3.2. Die konvexe Menge enthält somit keine Einbuchtungen.

Definition 3.3. Sei eine Teilmenge eines Vektorraumes V über . Die konvexe Hülle ist gegeben durch die Menge

Abbildung in dieser Leseprobe nicht enthalten

Die konvexe Hülle ist die kleinste konvexe Menge die enthält.

3.2 Simplex

Definition 3.4 ( – Simplex ). Sei und 𝑉 ein Vektorraum über . Es seien gegeben, sodass die Menge linear unabhängig ist. Dann heißt die Menge

Abbildung in dieser Leseprobe nicht enthalten

– Simplex oder Simplex und heißen Ecken .

Bemerkung 3.5. Jedes – Simplex besitzt Ecken.

Satz 3.6. Ein ist konvex, abgeschlossen und beschränkt.

Beweis. Die Konvexität und Beschränktheit folgt unmittelbar aus der Definition des Simplexes. Wir zeigen also nun kurz und knapp die Abgeschlossenheit, indem wir eine Folge benutzen. Dann ist

Abbildung in dieser Leseprobe nicht enthalten

wobei hier das k als ein weiteres Index zu verstehen ist. Des Weiteren ist

Abbildung in dieser Leseprobe nicht enthalten

Da S beschränkt ist, existiert eine konvergente Teilfolge nach dem Satz von Bolzano-Weierstraß , so dass

Abbildung in dieser Leseprobe nicht enthalten

Also gilt

Abbildung in dieser Leseprobe nicht enthalten

Mit

Abbildung in dieser Leseprobe nicht enthalten

S ist somit abgeschlossen.

Wenn wir die ersten drei Simplexe betrachten, erhalten wir folgende geometrische Darstellungen: Ein – Simplex stellt einen Punkt dar (dieser Simplex enthält nur eine Ecke, die dem Punkt in der geometrischen Darstellung entspricht). Ein – Simplex entspricht einer Strecke, die insgesamt zwei Ecken besitzt. Ein Dreieck bildet das – Simplex und ein – Simplex bildet ein Tetraeder. Wenn wir die Simplexe allgemein betrachten wollen, können wir das – Simplex als ein – dimensionales „Tetraeder“ bezeichnen, wobei es sich hier um die konvexe Hülle aus endlich vielen affin unabhängigen Punkten im handelt, die den Ecken des Simplex‘ entsprechen.

Bemerkung 3.7. Eine – Seite (auch 𝑘 – Facette genannt) eines – Simplex ist das – Simplex, welches durch die konvexe Hülle irgendeiner Teilmenge der Ecken gebildet wird. Die nulldimensionalen Seiten entsprechen den Eckpunkten, die – Seiten sind die Kanten und die – Seiten bezeichnet man als Seitenflächen.

Definition 3.8 . Eine endliche Folge

Abbildung in dieser Leseprobe nicht enthalten

von Simplexen heißt Triangulierung von S , falls

Abbildung in dieser Leseprobe nicht enthalten

und falls der Durchschnitt für , entweder leer ist oder eine gemeinsame – Seite mit Dimension bildet.

Nun sei eine Triangulation von gegeben. Im Folgenden werden die Ecken von mit den Labels beschriftet. Hierbei beachten wir folgende Regeln:

1) Die Ecken von S werden paarweise verschieden beschriftet
2) Die Ecken an den Seiten von S erhalten nur die Labels ihrer Ecken,
3) Die inneren Ecken können beliebig nach den Labels der Seiten beschriftet werden.

Somit können wir eine weitere Definition aufstellen:

Definition 3.9. Eine Beschriftung der Triangulierung eines Simplex‘ heißt dann Sperner-Beschriftung, falls die oben benannten Regeln eingehalten werden.

Diese Definition der Sperner – Beschriftung ist eine Generalisierung der aus

Kapitel 2 behandelten Definition für .

In den folgenden Abbildungen betrachten wir zwei Beispiele der 1- Sperner – Beschriftung und der 3 – Sperner –Beschriftung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5: Triangulierte Linie, die eine 1 – Sperner – Beschriftung darstellt

Abbildung in dieser Leseprobe nicht enthalten

Nicht abgebildet: Seiten mit der Nummer 3 sind im unteren Bereich, Seiten mit der Nummer 2 sind im hinteren Bereich

Abbildung 6: Trianguliertes Tetraeder, das eine 3 – Sperner – Beschriftung darstellt.

Definition 3.10. Ein elementares Simplex als Triangulierung bezeichnet man als voll beschrieben, wenn alle Ecken verschieden gefärbt oder nummeriert sind.

3.3 Lemma von Sperner

Nun ist es möglich Sperners Lemma für höhere Dimensionen aufzustellen:

Lemma 3.11 (Lemma von Sperner). Jede Triangulierung eines – Simplex‘ mit einer Sperner - Beschriftung besitzt eine ungerade Zahl an voll beschriebenen elementaren – Simplexe. Insbesondere existiert immer mindestens eins solcher Simplexe.

Es existieren viele Wege dieses Lemma zu beweisen. Im Folgenden werden wir eine Induktion über durchführen.

3.4. Beweis des Lemmas

Beweis. Man wähle eine Induktion über .

Induktionsanfang : Für handelt es sich um eine triangulierte Linie, die eine darstellt (wie in Abbildung 5 auf S.10 zu sehen). Die Anzahl der voll beschriebenen Simplexe ist ungerade.

Induktionsannahme: Die Anzahl der voll beschriebenen elementaren Simplexe sind immer ungerade.

[...]