Topologische Kombinatorik – einfach erklärt

Gegenstand und zentrale Ideen

Die topologische Kombinatorik ist ein im letzten Viertel des 20. Jahrhunderts entstandenes Teilgebiet der Mathematik. Sie verbindet Topologie und diskrete Mathematik in drei Richtungen: Topologische Methoden werden auf diskrete Probleme angewendet, Probleme der diskreten Geometrie werden topologisch verallgemeinert, und topologische Konzepte werden diskret nachgebildet.

Wichtige Gegenstände sind Halbordnungen und Simplizialkomplexe. Ein Simplizialkomplex besteht aus Punkten, Kanten, Dreiecken und höherdimensionalen Verallgemeinerungen samt ihren Seiten. Untersucht werden unter anderem Kollabierbarkeit und Schälbarkeit, also Verfahren zum schrittweisen Vereinfachen solcher Komplexe. Hinzu kommen Theoreme vom Borsuk-Ulam-Typ und ihre kombinatorischen Entsprechungen, die äquivariante Topologie zur Untersuchung symmetrischer Räume und Abbildungen sowie die Hindernistheorie, mit der die Existenz bestimmter Abbildungen geprüft wird.

Topologische Methoden für diskrete Probleme

Als Beginn der topologischen Kombinatorik gilt meist László Lovász’ topologischer Beweis der Kneservermutung von 1978. Martin Kneser hatte die Vermutung 1955 als Aufgabe veröffentlicht. Sie lautet: In jeder Partition der n-Teilmengen einer (2n+k)-Menge in k+1 Klassen gibt es eine Klasse, die ein disjunktes Paar von n-Mengen enthält.

Die Aussage lässt sich als Problem über die chromatische Zahl eines Knesergraphen formulieren. Die chromatische Zahl ist die kleinste Anzahl von Farben, mit denen die Knoten eines Graphen so gefärbt werden können, dass benachbarte Knoten verschiedene Farben erhalten. Lovász ordnete jedem Graphen G einen Simplizialkomplex N(G), den Nachbarschaftskomplex, zu. Sein Theorem von 1978 besagt: Ist die geometrische Realisierung von N(G) topologisch (k−1)-zusammenhängend, dann ist G nicht (k+1)-färbbar. Die geometrische Realisierung überführt dabei den abstrakten Simplizialkomplex in einen topologischen Raum.

Der Beweis verwendet im Kern den Satz von Borsuk-Ulam aus der algebraischen Topologie. Dass die Nachbarschaftskomplexe der Knesergraphen den benötigten Zusammenhang besitzen, kann durch ein Schälbarkeitsargument für die auftretenden Halbordnungen gezeigt werden. Die so gewonnenen unteren Schranken für chromatische Zahlen bilden einen wichtigen Forschungsbereich. Weitere Anwendungen betreffen andere graphentheoretische Probleme, Partitionen von Punktmengen im euklidischen Raum sowie Komplexitätsfragen, etwa evasive Grapheneigenschaften und Entscheidungsbaumalgorithmen.

Topologische Sätze besitzen teilweise diskrete Entsprechungen: Das Lemma von Sperner ist ein Analogon zum Brouwerschen Fixpunktsatz. Entsprechend ist das Lemma von Tucker ein Analogon zum Satz von Borsuk-Ulam; jeweils kann der eine Satz aus dem anderen hergeleitet werden.

Topologische Verallgemeinerungen der diskreten Geometrie

Ein zentrales Beispiel ist die topologische Verallgemeinerung des Satzes von Tverberg über Zerlegungen von Punktmengen und die Schnittpunkte ihrer konvexen Hüllen. Das Theorem von Murad Özaydin (1987), Karanbir Sarkaria (2000) und Alexei Volovikov (1996) lautet: Seien d≥1, q=pᵏ eine Primpotenz und N=(q−1)(d+1). Für jede stetige Abbildung f: Δᴺ→ℝᵈ des Standard-N-Simplexes in ℝᵈ existieren q paarweise disjunkte Seiten σ₁,…,σq⊂Δᴺ, sodass f(σ₁)∩⋯∩f(σq) nicht leer ist.

Die Frage, ob die Aussage auch gilt, wenn q keine Primpotenz ist, wird im Artikel als offenes kontinuierliches Tverberg-Problem bezeichnet. Den Primzahlfall k=1 bewiesen Imre Bárány, S. B. Shlosman und A. Szücs 1981. Das entscheidende Werkzeug ihres Beweises geht im Wesentlichen auf einen Satz von Dold zurück, der den Satz von Borsuk-Ulam verallgemeinert.

Dolds Theorem von 1983 besagt: Sei G eine nicht-triviale endliche Gruppe und seien X und Y topologische Räume mit freier G-Wirkung, das heißt, außer dem neutralen Element fixiert kein Gruppenelement einen Punkt. Ist X (n−1)-zusammenhängend, hat Y die Dimension m und existiert eine G-äquivariante Abbildung von X nach Y, also eine mit den Gruppenwirkungen verträgliche Abbildung, dann gilt m≥n. Dieses Theorem wurde zu einem wichtigen Werkzeug der topologischen Kombinatorik.

Weitere Themen sind faires Teilen und Massenpartitionen, darunter das Splitting Necklace Theorem von Noga Alon. Diese Probleme haben auch algorithmische Seiten und enthalten diskrete Versionen von Sätzen des Borsuk-Ulam-Typs.

Diskrete Morsetheorie und diskrete Krümmung

Die diskrete Morsetheorie überträgt Ideen der Morsetheorie für differenzierbare Mannigfaltigkeiten auf Simplizialkomplexe. Dazu betrachtet sie diskrete Morsefunktionen, die den Simplizes unter bestimmten Nebenbedingungen reelle Werte zuordnen. Kritische Simplizes spielen dabei eine ähnliche Rolle wie kritische Punkte in der kontinuierlichen Morsetheorie.

Ein Beispiel entsteht aus Graphen auf einer festen n-elementigen Knotenmenge V. Ein Graph G=(V,E) wird mit seiner Kantenmenge E identifiziert. Alle Graphen auf V, die nicht 2-zusammenhängend sind, bilden dadurch einen Simplizialkomplex Δₙ². Ein Graph ist 2-zusammenhängend, wenn er zusammenhängend bleibt, nachdem ein einzelner Knoten entfernt wurde. Die Topologie von Komplexen, die mit Grapheneigenschaften verbunden sind, ist unter anderem für Vassilievs Theorie der Knoteninvarianten wichtig.

Ein Theorem von Eric Babson et al. (1999) und Victor Turchin (1997) besagt: Für n≥3 hat die geometrische Realisierung von Δₙ² den Homotopietyp eines Wedges aus (n−2)! Sphären der Dimension 2n−5. Ein Wedge ist ein Raum, der entsteht, indem die Sphären an jeweils einem Punkt zusammengefügt werden. Im Beweis konstruieren Babson et al. eine diskrete Morsefunktion mit genau einer kritischen 0-Zelle. Damit zeigen sie, dass die geometrische Realisierung eines bestimmten Simplizialkomplexes zusammenziehbar ist.

Die grundlegende Verbindung zwischen kritischen Simplizes und der Gestalt eines Raumes formuliert ein Theorem von Robin Forman aus dem Jahr 1995: Besitzt ein Simplizialkomplex Δ eine diskrete Morsefunktion, dann ist seine geometrische Realisierung homotopieäquivalent zu einem CW-Komplex mit genau einer Zelle der Dimension p für jeden kritischen Simplex der Dimension p. Homotopieäquivalent bedeutet, dass sich die Räume aus topologischer Sicht stetig ineinander verformen lassen. Ein weiteres wichtiges Forschungsgebiet ist die Diskretisierung des Krümmungsbegriffs.