- Kneservermutung
-
Der Titel dieses Artikels ist mehrdeutig. Das in der Vergangenheit als Kombinatorische Topologie bezeichnete mathematische Fachgebiet findet sich unter Algebraische Topologie. - Anwendungen von Methoden aus der Topologie auf Probleme der diskreten Mathematik,
- topologische Verallgemeinerungen von Problemen der diskreten Geometrie,
- die Diskretisierung topologischer Konzepte.
- Jiří Matoušek: Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer-Verlag, Berlin/New York 2003, ISBN 978-3540003625.
- ↑ Martin Kneser. Aufgabe 360. Jahresbericht der DMV, 58(2): 27, 1955.
- ↑ Mark de Longueville. 25 Jahre Beweis der Kneservermutung - Der Beginn der topologischen Kombinatorik pdf, DMV-Mitteilungen 4, 8 - 11, 2003.
- ↑ Anders Björner. Topological Methods. In R. Graham, M. Grötschel, L. Lovász (Ed.), Handbook of Combinatorics. North Holland, Amsterdam, 1819 - 1872, 1994.
- ↑ 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.
- ↑ Robin Forman. Combinatorial differential topology and geometry. In L. Billera et al. (Ed.), New perspectives in algebraic combinatorics, Cambridge University Press, MSRI Publ. 38, 177 - 206, 1999.
Die Topologische Kombinatorik ist ein jüngeres Fachgebiet der Mathematik, welches im letzten Quartal des 20. Jahrhunderts entstanden ist und sich mit folgenden Typen von Problemen beschäftigt:
Die topologische Kombinatorik ist damit gewissermaßen eine Umkehrung der kombinatorischen Topologie, einem Fachgebiet, das sich mit der Anwendung kombinatorischer Methoden in der Topologie beschäftigte und Anfang des 20. Jahrhunderts in der algebraischen Topologie aufgegangen ist.
Eine wichtige Rolle in der topologischen Kombinatorik spielen – unter anderem – Themen wie die Topologie von Halbordnungen und Simplizialkomplexen, Kollabierbarkeit und Schälbarkeit, Theoreme vom Borsuk-Ulam-Typ und ihre kombinatorischen Analoga, äquivariante Topologie und Hindernistheorie.
Konkrete Beispiele für die oben genannten Problemtypen werden im Folgenden aufgeführt.
Inhaltsverzeichnis |
Anwendungen von Methoden aus der Topologie auf Probleme der diskreten Mathematik
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 n-Teilmengen einer (2n + k)-Menge in k + 1 Klassen existiert eine Klasse, die ein disjunktes Paar von 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 G einen Simplizialkomplex N(G), den sogenannten Nachbarschaftskomplex, zuzuordnen und das folgende Theorem zu etablieren [2].
Theorem (Lovász 1978): Sei G ein Graph mit Nachbarschaftskomplex N(G). Ist die geometrische Realisierung von N(G) topologisch (k − 1)-zusammenhängend, dann ist der Graph G nicht (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.
Topologische Verallgemeinerungen von Problemen der diskreten Geometrie
Eine topologische Verallgemeinerung eines Theorems von Helge Tverberg über Partitionen von Punktmengen im euklidischen Raum und deren konvexe Hüllen ist das folgende.
Theorem (Özaydin 1987, Sarkaria 2000, Volovikov 1996). Seien 
, q = pk eine Primpotenz und N = (q − 1)(d + 1). Für jede stetige Abbildung 
des standard-N-Simplexes in den 
existieren q paarweise disjunkte Seiten 
, so dass der Durchschnitt 
nicht leer ist.
Die offene Frage, ob dieses Theorem auch für den Fall, dass q keine Primpotenz ist, ist bekannt als das kontinuierliche Tverberg-Problem. Der Primzahlfall, also der Fall k = 1, wurde von Bárány, Schlosman und Szücs 1981 gezeigt. 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 [4].
Theorem (Dold 1983). Sei G eine nicht-triviale endliche Gruppe, X und Y (hinreichend nette) topologische Räume mit freier G-Wirkung. Ferner sei X (n − 1)-zusammenhängend und die Dimension von Y gleich m. Falls eine G-äquivariante Abbildung von X nach Y existiert, so gilt 
.
Weitere Beschäftigungsfelder in diesem Teilgebiet sind unter anderem Probleme des fairen Teilens und Massenpartitionsprobleme (hierunter auch das Splitting Necklace Theorem). Diese Probleme berühren auch algorithmische Fragestellungen und beinhalten diskrete Versionen von Sätzen vom Borsuk-Ulam-Typ.
Diskretisierung topologischer Konzepte
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 V eine feste n-Menge. Identifiziere einen Graphen G = (V,E) auf der Knotenmenge V mit der Kantenmenge E. Mit Hilfe dieser Identifikation bilden alle Graphen mit Knotenmenge V, die nicht 2-zusammenhängend sind, einen Simplizialkomplex, den wir mit 
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 – zu untersuchen.
Theorem (Babson et al. 1999, Turchin 1997). Für 
hat die geometrische Realisierung von den Homotopietyp eines Wedges von (n − 2)! Sphären der Dimension 2n − 5.
Im Verlauf des Beweises konstruieren Babson et al. eine diskrete Morsefunktion mit genau einer kritischen 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 (Forman 1995). Angenommen Δ ist ein Simplizialkomplex mit einer diskreten Morsefunktion, dann ist die geometrische Realisierung von Δ homotopieäquivalent zu einem CW-Komplex mit genau einer Zelle der Dimension p für jeden kritischen Simplex der Dimension p.
Ein weiteres wichtiges Forschungsgebiet umfasst Diskretisierungen des Krümmungsbegriffes [5].
Literatur
Referenzen
Wikimedia Foundation.
