Tucker's lemma

rdf:langString Lemma von Tucker

rdf:langString Das Lemma von Tucker ist ein Satz der Kombinatorik, der äquivalent zum Satz von Borsuk-Ulam aus der Topologie ist, aufgestellt von Albert W. Tucker. Sei T eine Triangulation des abgeschlossenen n-Balls , die auf dem Rand, der Sphäre , antipodale Symmetrie hat (das heißt die Simplices von T in liefern eine Triangulation von , in der mit dem Simplex auch ist). Sei außerdem eine Nummerierung der Knoten von T, die auf eine ungerade Funktion ist (das heißt für jeden Knoten ). Nach dem Lemma von Tucker enthält dann T mit Nummerierung L eine komplementäre Kante, das heißt eine Kante mit Nummerierung der zugehörigen Knoten Ein Vergleich mit dem Satz von Borsuk-Ulam in folgender Version zeigt die Analogie: Satz von Borsuk-Ulam: Sei eine stetige Abbildung, so dass auf dem Rand die Funktion antipodal ist. Dann gibt es ein mit . Das Lemma von Tucker folgt aus dem Satz von Borsuk-Ulam und umgekehrt (ähnlich wie Brouwers Fixpunktsatz aus dem Lemma von Sperner und umgekehrt). Robert Freund und Michael Todd fanden einen konstruktiven Beweis des Lemmas von Tucker, der auch einen Algorithmus lieferte um die komplementäre Kante zu finden. Das Lemma von Ky Fan ist eine Verallgemeinerung des Lemmas von Tucker: Lemma von Ky Fan: Es gelten dieselben Voraussetzungen und Definitionen wie beim Lemma von Tucker, außer dass L keiner Beschränkung der Anzahl der verschiedenen Nummern unterliegt. Gibt es keine komplementäre Kante, so enthält (T, L) eine ungerade Anzahl alternierender n-dimensionaler Simplices. Ein Simplex heißt dabei alternierend, falls alle Nummern der Knoten untereinander betragsmäßig verschieden sind und deren Vorzeichen wechseln. Da ein n-dimensionaler Simplex (n+1) Knoten hat müssen für einen alternierenden Simplex (n+1) betragsmäßig verschiedene Nummern vorhanden sein, es gibt aber unter den Voraussetzungen des Lemmas von Tucker nur n betragsmäßig verschiedene Nummern. Also gibt es in diesem Fall keinen alternierenden Simplex in (T, L) und das Lemma von Tucker folgt als Korollar zum Lemma von Ky Fan.