Wigderson Group

Extremale Kombinatorik und Ramsey-Theorie

Die extremale Kombinatorik untersucht die Größe und Struktur diskreter Objekte, die natürlichen Beschränkungen unterliegen. Zu den untersuchten diskreten Objekten gehören beispielsweise Mengen von ganzen Zahlen, Sammlungen von Punkten und Geraden in einer Ebene, lineare Räume von Matrizen und Graphen, d. h. Sammlungen von Knoten, von denen einige Paare durch eine Kante verbunden sind. Während ein Graph mit n Knoten bis zu (n²-n)/2 Kanten haben kann, sinkt die maximal mögliche Anzahl von Kanten erheblich, wenn wir dem Graphen bestimmte Beschränkungen auferlegen; wenn wir beispielsweise verlangen, dass der Graph keine Zyklen enthält, sinkt die maximal mögliche Anzahl von Kanten auf n-1. Wir könnten auch verfeinerte Fragen stellen: Anstatt alle Zyklen auszuschließen, können wir nur Zyklen einer bestimmten Länge ausschließen und erneut nach der maximal möglichen Anzahl von Kanten fragen. Für den Ausschluss von Zyklen der Länge 3 ist die Antwort seit über 100 Jahren bekannt. Für die Länge 4 ist die Antwort seit über 80 Jahren bekannt. Für die Längen 5, 6 und 7 ist die Antwort seit über 50 Jahren bekannt. Aber für die Länge 8 haben wir immer noch keine Ahnung, wie die Antwort lautet!

Obwohl viele grundlegende Probleme der extremalen Kombinatorik noch ungelöst sind, hat dieses Gebiet in den letzten Jahrzehnten erhebliche Fortschritte gemacht. Viele der spannendsten Entwicklungen basieren auf Ideen aus einer Vielzahl anderer Fachgebiete. Dazu gehören Algebra, Ergodentheorie, Funktionalanalysis, Zahlentheorie, Probabilistik, theoretische Informatik und Topologie. Dies hat zu einer fruchtbaren Wechselwirkung zwischen diesen Fachgebieten und der extremalen Kombinatorik geführt. Durch die Einbeziehung von Ideen aus verschiedenen Bereichen versucht die Wigderson Gruppe, grundlegende Fragen zur Struktur diskreter Objekte sowie zu Ordnung und Chaos in großen Systemen zu beantworten.