Zufallsgraphen: Kerne, Färbungen und Ausbreitung

• Antragsteller: Professor Dr. Amin Coja-Oghlan
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2018 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 397269007

Seit den bahnbrechenden Arbeiten von Paul Erdos und Alfred Renyi aus der Mitte des letzten Jahrhunderts ist das Studium von Zufallsgraphen von grundlegendem Interesse in der Kombinatorik. Zufallsgraphen werden in der Extremalen Kombinatorik verwendet, um Objekte mit scheinbar widersprüchlichen Eigenschaften zu konstruieren, wie sie etwa in der Ramseytheorie benötigt werden. Ein sehr bekannter neuerer Beitrag dieser Art ist die Arbeit von Bohman und Keevash (2013) zum dreiecksfreien Zufallsgraphenprozess, welche eine Schranke an die Ramseyzahl R(3,k) liefert. Andere Anwendungen ergeben sich in der Informatik, wo zufällige (Hyper-)Graphen im Hashing Verwendung finden (Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh, Rink 2010), sowie in der Konstruktion fehlerkorrigierender Kodes (z.B. Giurgiu, Macris, Urbanke 2016). Weiterhin spielen Zufallsgraphen eine wichtige Rolle im Studium komplexer Netzwerke (z.B. van der Hofstand 2016). Trotz ihrer enormen Bedeutung in der Kombinatorik, der Informatik und vielen anderen Disziplinen sind wichtige Eigenschaften von Zufallsgraphen bisher nicht gut verstanden. Das Ziel dieses Projektes, bei welchem es sich um ein gemeinsame D-A-CH-Bewerbung von Amin Coja-Oghlan (Goethe-Universität Frankfurt am Main) und Mihyun Kang (Technische Universität Graz) handelt, ist, mithilfe der modernen mathematischen Methoden, die uns gemeinsam zur Verfügung stehen, deutliche Fortschritte in Bezug auf mehrere grundlegende und in manchen Fällen seit langem offenstehende Probleme zu machen. Konkrete Beispiele sind etwa das k-Kern-Problem, vielleicht die natürlichste Verallgemeinerung des Zusammenhangskomponentenproblems, das bereits Erdos und Renyi studiert haben, das Problem der Färbungszahl zufälliger Graphen, welches Erdos und Renyi bereits 1960 als offenes Problem benannt haben, und das Ausbreitungsproblem von Kaskadeneffekten.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Österreich
• Partnerorganisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
• Kooperationspartnerin: Professorin Dr. Mihyun Kang