Kombinatorik und Graphentheorie
Die Fragen der Kombinatorik lassen sich bis in die Anfänge der Mathematik zurückverfolgen. Es geht hauptsächlich um Probleme mit endlichen, aber dennoch großen Objekten wie (Hyper-)Graphen, Permutationen, lateinischen Quadraten und Partitionen von Mengen.
Viele kombinatorische Fragen haben ein gemeinsames Merkmal: Sie sind sehr einfach zu formulieren, auch für Nicht-Mathematiker, aber sie widerstehen jahrzehntelang jedem Versuch, sie zu knacken. Eine dieser Fragen, die inzwischen gelöst ist, ist das Problem, ob jede Karte so mit vier Farben eingefärbt werden kann, dass jedes Land eine dieser vier Farben erhält und jedes Länderpaar, das durch eine gemeinsame Grenze verbunden ist, zwei unterschiedliche Farben aufweist (Vier-Farben-Theorem).
Viele Entwicklungen der letzten Jahrzehnte beruhen auf der Nutzung von Werkzeugen aus anderen Bereichen wie der Wahrscheinlichkeitstheorie, der Analysis, der Zahlentheorie, der Ergodentheorie und der Algebra.
Hier in Heidelberg beschäftigen wir uns hauptsächlich mit Graphen und Hypergraphen. Hypergraphen sind einfach Teilmengen der Potenzmenge einer endlichen Menge. Die endliche Menge wird als Knotenmenge bezeichnet, während die Elemente der Untermenge als Kanten bezeichnet werden. In den meisten Fällen betrachten wir einheitliche Hypergraphen, d. h. jede Kante enthält die gleiche Anzahl von Elementen. Wenn alle Kanten die Größe 2 haben, dann wird der Hypergraph als Graph bezeichnet. Das oben erwähnte Vier-Farben-Theorem kann als Partitionsfrage für die Knotenmenge einer bestimmten Klasse von Graphen (planare Graphen) umformuliert werden, wobei das Ziel darin besteht, die Knotenmenge so in vier Klassen zu unterteilen, dass keine Kante innerhalb einer Knotenklasse liegt.
In unseren Beweisen verwenden wir häufig randomisierte Ansätze. Zu diesem Zweck entwerfen wir einen Zufallsprozess, der sich im Laufe der Zeit weiterentwickelt und so ein kombinatorisches Objekt konstruiert, und wir versuchen, das typische Ergebnis eines solchen Zufallsprozesses zu analysieren. In der Vergangenheit hat sich dieser Ansatz als äußerst erfolgreich erwiesen und wird als probabilistische Methode bezeichnet.
Eine Kernkompetenz unserer Forschungsgruppe betrifft Fragen, die sich mit der Suche nach hinreichenden Bedingungen befassen, welche es uns erlauben, besonders schöne Untergraphen eines großen Ausgangsgraphen zu finden und zu entscheiden, wann ein großer Graph eine Zerlegung in kleine vordefinierte Graphen zulässt.