Wie viele Kanten garantieren ein Muster?

Abstract:
Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten, wobei jede Kante ein Paar von Knoten darstellt. Graphen bilden ein vielfältig anwendbares Modell symmetrischer binärer Relationen, die in der Praxis im Kontext verschiedenster Netzwerke auftreten, seien es Computer- oder Transportnetzwerke, chemische, oder soziale Netzwerke.

Welche Anzahl von Kanten garantiert insgesamt, dass ein Graph auf n Knoten sicher eine bestimmtes kleines Muster enthält, etwa ein Dreieck? Ein Zykel der Länge vier? Oder einen vollständigen Graphen auf vier Knoten? Wie sieht es mit anderen Mustern aus?

Dies ist die Theorie der Turán-Zahlen, einem klassischen Thema der Graphentheorie mit vielen interessanten Sätzen und noch mehr spannenden offenen Problemen. Sie bietet eine große Verhaltensvielfalt und ein reiches Arsenal an Beweismethoden. Der Vortrag gibt eine Einführung in diese Theorie. Besondere Vorkenntnisse über Graphen sind nicht erforderlich.