Topologische Kombinatorik

Der Beweis der Kneservermutung durch László Lovász 1978 mit Hilfe topologischer Methoden wird gemeinhin als der Beginn der topologischen Kombinatorik angesehen. Martin Kneser veröffentlichte diese Vermutung 1955 im Jahresbericht der DMV in Form einer Aufgabe.[1]

Kneservermutung: In jeder Partition der ${\displaystyle n}$-Teilmengen einer ${\displaystyle (2n+k)}$-Menge in ${\displaystyle k+1}$ Klassen existiert eine Klasse, die ein disjunktes Paar von ${\displaystyle n}$-Mengen enthält.

Diese Aussage lässt sich leicht in ein Problem über die chromatische Zahl einer gewissen Familie von Graphen – den Knesergraphen – umformulieren. Lovász' bahnbrechende Idee war nun, jedem Graphen ${\displaystyle G}$ einen Simplizialkomplex ${\displaystyle N(G)}$, den sogenannten Nachbarschaftskomplex, zuzuordnen und das folgende Theorem zu etablieren[2].

Nachbarschaftskomplex des Kneser Graphen KG(5,2)

Theorem (Lovász 1978): Sei ${\displaystyle G}$ ein Graph mit Nachbarschaftskomplex ${\displaystyle N(G)}$. Ist die geometrische Realisierung von ${\displaystyle N(G)}$ topologisch ${\displaystyle (k-1)}$-zusammenhängend, dann ist der Graph ${\displaystyle G}$ nicht ${\displaystyle (k+1)}$-färbbar.

Der Kern des Beweises dieses Theorems ist der Satz von Borsuk-Ulam aus der algebraischen Topologie. Der Beweis, dass die Nachbarschaftskomplexe der Knesergraphen tatsächlich den richtigen topologischen Zusammenhang aufweisen, ist leicht durch ein Schälbarkeitsargument – angewandt auf die auftauchenden Halbordnungen – erbracht (siehe beispielsweise[3]).

Die Etablierung unterer Schranken für die chromatische Zahl eines Graphen hat einen großen Stellenwert in der Forschungsliteratur in diesem Teil der topologischen Kombinatorik. Weitere Forschungsaktivitäten handeln von anderweitigen Problemen der Graphentheorie, von Partitionsresultaten von Punktmengen im euklidischen Raum und von Komplexitätsresultaten, beispielsweise für evasive Grapheneigenschaften und Entscheidungsbaumalgorithmen.

Ähnlich wie der Fixpunktsatz von Brouwer sein Analogon in der diskreten Geometrie im Lemma von Sperner hat (die Ableitung des Brouwerschen Fixpunktsatzes aus dem Lemma von Sperner wurde in Das Buch der Beweise, Kapitel 25, aufgenommen), hat der Satz von Borsuk-Ulam ein Analogon im Lemma von Tucker (das heißt der eine Satz folgt aus dem anderen und umgekehrt).

Eine topologische Verallgemeinerung des nach Helge Tverberg benannten Satzes von Tverberg über Zerlegungen von Punktmengen im euklidischen Raum und deren konvexe Hüllen ist das folgende.

Theorem (Murad Özaydin 1987, Karanbir Sarkaria 2000, Alexei Volovikov 1996). Seien ${\displaystyle d\geq 1}$, ${\displaystyle q=p^{k}}$ eine Primpotenz und ${\displaystyle N=(q-1)(d+1)}$. Für jede stetige Abbildung ${\displaystyle f\colon \Delta ^{N}\rightarrow \mathbb {R} ^{d}}$ des Standard-${\displaystyle N}$-Simplexes in den ${\displaystyle \mathbb {R} ^{d}}$ existieren ${\displaystyle q}$ paarweise disjunkte Seiten ${\displaystyle \sigma _{1},\ldots ,\sigma _{q}\subset \Delta ^{N}}$, so dass der Durchschnitt ${\displaystyle f(\sigma _{1})\cap \cdots \cap f(\sigma _{q})}$ nicht leer ist.

Die offene Frage, ob dieses Theorem auch für den Fall gilt, dass ${\displaystyle q}$ keine Primpotenz ist, ist bekannt als das kontinuierliche Tverberg-Problem. Der Primzahlfall, also der Fall ${\displaystyle k=1}$, wurde von Imre Bárány, S. B. Shlosman und A. Szücs 1981 gezeigt[4]. Das topologische Werkzeug, welches in deren Beweis die entscheidende Rolle gespielt hat, geht im Wesentlichen auf einen Satz von Dold zurück, der eine Verallgemeinerung des Satzes von Borsuk-Ulam ist. Dolds Theorem wurde zu einem äußerst wichtigen und erfolgreichen Werkzeug in der topologischen Kombinatorik[5].

Theorem (Albrecht Dold 1983). Sei ${\displaystyle G}$ eine nicht-triviale endliche Gruppe, ${\displaystyle X}$ und ${\displaystyle Y}$ topologische Räume mit freier ${\displaystyle G}$-Wirkung. Ferner sei ${\displaystyle X}$ ${\displaystyle (n-1)}$-zusammenhängend und die Dimension von ${\displaystyle Y}$ gleich ${\displaystyle m}$. Falls eine ${\displaystyle G}$-äquivariante Abbildung von ${\displaystyle X}$ nach ${\displaystyle Y}$ existiert, so gilt ${\displaystyle m\geq n}$.

Weitere Beschäftigungsfelder in diesem Teilgebiet sind unter anderem Probleme des fairen Teilens und Massenpartitionsprobleme (hierunter auch das Splitting Necklace Theorem von Noga Alon). Diese Probleme berühren auch algorithmische Fragestellungen und beinhalten diskrete Versionen von Sätzen vom Borsuk-Ulam-Typ.

Diskrete Morsetheorie ist eine diskrete Version der Morsetheorie aus dem Gebiet der differenzierbaren Mannigfaltigkeiten. Ähnlich zur Morsetheorie werden in der diskreten Morsetheorie Funktionen betrachtet, die Simplizes reelle Werte unter gewissen Nebenbedingungen zuordnen. Eine Anwendung der diskreten Morsetheorie ist die folgende.

Sei ${\displaystyle V}$ eine feste ${\displaystyle n}$-Menge. Identifiziere einen Graphen ${\displaystyle G=(V,E)}$ auf der Knotenmenge ${\displaystyle V}$ mit der Kantenmenge ${\displaystyle E}$. Mit Hilfe dieser Identifikation bilden alle Graphen mit Knotenmenge ${\displaystyle V}$, die nicht ${\displaystyle 2}$-zusammenhängend sind, einen Simplizialkomplex, den wir mit ${\displaystyle \Delta _{n}^{2}}$ bezeichnen wollen. Beispielsweise in Vassilievs Theorie der Knoteninvarianten ist es von Bedeutung, die Topologie von Simplizialkomplexen, die mit gewissen Grapheneigenschaften assoziiert sind – wie zum Beispiel ${\displaystyle \Delta _{n}^{2}}$ – zu untersuchen.

Theorem (Eric Babson et al. 1999,[6] Victor Turchin 1997).[7] Für ${\displaystyle n\geq 3}$ hat die geometrische Realisierung von ${\displaystyle \Delta _{n}^{2}}$ den Homotopietyp eines Wedges von ${\displaystyle (n-2)!}$ Sphären der Dimension ${\displaystyle 2n-5}$.

Im Verlauf des Beweises konstruieren Babson et al. eine diskrete Morsefunktion mit genau einer kritischen ${\displaystyle 0}$-Zelle, um zu zeigen, dass die geometrische Realisierung eines gewissen Simplizialkomplexes zusammenziehbar ist.

Die Analogien zwischen der kontinuierlichen und der diskreten Morsetheorie sind weitreichend. Ein wichtiges Beispiel hierfür ist die folgende Aussage.

Theorem (Robin Forman 1995).[8] Angenommen ${\displaystyle \Delta }$ ist ein Simplizialkomplex mit einer diskreten Morsefunktion, dann ist die geometrische Realisierung von ${\displaystyle \Delta }$ homotopieäquivalent zu einem CW-Komplex mit genau einer Zelle der Dimension ${\displaystyle p}$ für jeden kritischen Simplex der Dimension ${\displaystyle p}$.

Ein weiteres wichtiges Forschungsgebiet umfasst Diskretisierungen des Krümmungsbegriffes[9].

• Jiří Matoušek: Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry. Springer-Verlag, Berlin u. a. 2003, ISBN 3-540-00362-2 (Universitext).
• Mark de Longueville: A Course in Topological Combinatorics. Springer New York, 2012, ISBN 978-1441979094 (Universitext).
• Dmitry Kozlov: Combinatorial Algebraic Topology, Springer 2007

1. Martin Kneser. Aufgabe 360. Jahresbericht der DMV, 58(2): 27, 1955.
2. Mark de Longueville. 25 Jahre Beweis der Kneservermutung - Der Beginn der topologischen Kombinatorik pdf, DMV-Mitteilungen 4, 8 - 11, 2003.
3. Anders Björner. Topological Methods. In R. Graham, M. Grötschel, L. Lovász (Ed.), Handbook of Combinatorics. North Holland, Amsterdam, 1819 - 1872, 1994.
4. I. Bárány, S. B. Shlosman, A. Szucs On a topological generalization of a theorem of Tverberg, J. London Math. Soc. (2), Band 23, 1981, S. 158–164
5. Jiří Matoušek. Using the Borsuk-Ulam Theorem. Lectures on topological methods in combinatorics and geometry. In Kollaboration mit Anders Björner und Günter M. Ziegler geschrieben. Universitext, Springer, Heidelberg, 2003.
6. Eric Babson, Anders Björner, Svante Linusson, John Shareshian, Volkmar Welker: Complexes of not i-connected graphs, Topology, Band 38, 1999, S. 271–299
7. Turchin, Homology of Complexes of 2-Connected Graphs, Russ. Math. Surveys, Band 52, 1997, S. 426–427.
8. Forman, A discrete Morse theory for cell complexes, in: S. T. Yau (Hrsg.), Geometry, Topology & Physics for Raoul Bott, International Press, 1995.
9. Robin Forman. Combinatorial differential topology and geometry. In Louis Billera et al. (Ed.), New perspectives in algebraic combinatorics, Cambridge University Press, MSRI Publ. 38, 177 - 206, 1999.