Zufallsgraphen: Kerne, Färbungen und Ausbreitung

Graphen sind mathematische Modelle von Netzwerken, wie sie in den Natur- und Wirtschaftswissenschaften oder der Informatik vorkommen. Häufig kann die Evolution von Netzwerken mit Hilfe von Zufallsprozessen beschrieben werden. Dies motiviert das Studium von Zufallsgraphen. Ferner hat sich herausgestellt, dass Zufallsgraphen an sich extrem strukturreiche und nützliche mathematische Objekte mit zahlreichen Anwendungen in anderen Teilgebieten der Mathematik wie etwa der Informationstheorie oder der Ramseytheorie sind. Das systematische Studium von Zufallsgraphen begann 1960 mit der Arbeit der ungarischen Mathematiker Paul Erdos und Alfred Renyi. Jedoch sind bis heute viele Eigenschaften von Zufallsgraphen nur unzureichend verstanden. Ziel dieses Kollaborationsprojektes, welches gemeinsam an der Goethe-Universtiät in Frankfurt am Main (Deutschland) und an der TU Graz (Österreich) durchgeführt wird, ist, das exakte mathematische Verständnis von Zufallsgraphen mit Hilfe moderner mathmatischer Werkzeuge aus beispielsweise Enumerativer Kombinatorik oder der Theorie der Graphlimiten voranzutreiben. Insbesondere wird das Graphenfärbungsproblem auf zufälligen Graphen untersucht sowie die Verteilung stark zusammenhängender Unterstrukturen, sogenannter Kerne, und die Ausbreitung kaskadierender Ereignisse. Das Graphenfärbungsproblem beispielsweise ist seit der brühmten Vierfarbenvermutung von Gutherie (1852) ein zentrales mathematisches Forschungsthema. Kerne haben Anwendungen etwa in der Kodierungstheorie und das Ausbreitungsproblem ist ein zentrales Thema im Studium komplexer sozialer oder künstlicher Netzwerke.

Das wichtigste Thema des Forschungsprojekts ist die Theorie der Zufallsgraphen. Dieses spannende Gebiet an der Schnittstelle von Kombinatorik und Wahrscheinlichkeitstheorie wurde in den 1960er Jahren von Erds und Rényi initiiert. Zufallsgraphen haben seitdem Auswirkungen auf eine Vielzahl anderer Disziplinen, darunter Informatik, Statistik, statistische Physik und Netzwerkwissenschaften. In diesem Projekt haben wir Fortschritte bei wichtigen offenen Problemen zu Kernen, Färbungen und Ausbreitung gemacht. Kerne. Das wegweisende Ergebnis der Zufallsgraphentheorie, welches das Gebiet als Ganzes begründete, war die Arbeit von Erds und Rényi über die Entwicklung der Zusammenhangskomponenten von Zufallsgraphen. Kerne sind natürliche Verallgemeinerungen von Zusammenhangskomponenten. In diesem Projekt haben wir Kernstrukturen untersucht, die sich aus einer dünn besetzten Paritätsmatrix ergeben. Ein wichtiger Bestandteil für den Beweis dieses Ergebnisses ist die Analyse des Warning Propagation Message Passing Algorithmus, eines allgegenwärtigen kombinatorischen Message Passing Algorithmus von zentraler Bedeutung für die physikalische Sicht auf zufällige kombinatorische Strukturen. Färbungen. Das Färben von Graphen ist eines der bekanntesten und vielleicht auch reizvollsten Probleme der Kombinatorik. Die chromatische Zahl eines Graphen ist die kleinste Anzahl von Farben, mit denen der Graph gefärbt werden kann. Das Problem, die chromatische Zahl von Zufallsgraphen zu finden, ist eines der am längsten offenen Probleme in der Zufallsgraphentheorie. In diesem Projekt haben wir Fortschritte bei diesem grundlegenden kombinatorischen Problem gemacht. Wir haben das klassische Ergebnis von Bollobs zur Asymptotik der chromatischen Zahl des binomialen Zufallsgraphen auf das stochastische Blockmodell und auf Graphons verallgemeinert. Ausbreitung. Die Herausforderungen im Zusammenhang mit der Modellierung der Coronavirus-Pandemie zeigen die zentrale Bedeutung des Verständnisses von Ausbreitungsprozessen in Netzwerken. In diesem Projekt haben wir die Mehrheitsdynamik auf Zufallsgraphen untersucht, welche nahe mit Ansteckungsprozessen verwandt ist. Wir haben eine Vermutung zur Mehrheitsdynamik auf dem Erds-Rényi-Zufallsgraphen gelöst, die im Jahr 2016 von Benjamini et al. aufgestellt wurde. Wir wurden von der Zeitschrift Random Structures & Algorithms darüber informiert, dass dieses Papier zu den 10 am häufigsten heruntergeladenen Papers gehört, die in der Zeitschrift in den Jahren 2019-2020 veröffentlicht wurden. Wir sehen keine unmittelbaren Auswirkungen des Projekts über den wissenschaftlichen Bereich hinaus, da sich das Projekt mit grundlegenden/theoretischen Mathematikproblemen befasste. Es könnte jedoch Anwendungen in anderen Bereichen geben, wie z. B. sozialen Netzwerken und Epidemien auf Netzwerken.