Dünne zufällige kombinatorische Strukturen

• Antragsteller: Professor Dr. Amin Coja-Oghlan
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 517012267

KontextIn der probabilistischen Kombinatorik geht es um das Studium zufälliger kombinatorischer Strukturen wie zufälliger Graphen, Netzwerke oder Matrizen. Solche Objketen spielen eine entscheidende Rolle in randomisierten Konstruktionen in der Informatik und anderen Gebieten. Im Verlauf der letzten 20 Jahre hat die probabilistische Kombinatorik wichtige Impulse aus der statistischen Physik erhalten, wo die heuristische "Kavitätsmethode" entwickelt wurde. Auf ihrer Grundlage wurden exakte Vermutungen zu mehreren bekannten offenen Problemen hergeleitet. Ziel dieses Projektes ist es, eine rigorose mathematische Basis für diese bislang heuristischen Techniken zu schaffen.ZieleDer Schwerpunkt liegt auf dünnen zufälligen Strukturen. Genauer befassen wir uns mit drei prominenten und eng verwobenen Fragestellungen:1. zufällige kombinatorische Matrizen und zufällige Gleichungen über diskreten algebraischen Strukturen2. gewichtete Paarungen in dünnen zufälligen Graphen3. Hamiltonkreise in dünnen zufälligen GraphenJeweils werden wir Ideen aus der statistischen Physik zur Entwicklung neue mathematischer Techniken heranziehen, um so die Vermutungen aus der Physik rigoros zu untersuchen.Im ersten Punkt geht es darum, exakte notwendige und hinreichende Bedingungen dafür herzuleiten, dass eine dünn besetzte zufällige kombinatorische Matrix vollen Rang hat. Ferner beabsichtigen wir, zufällige Gleichungssysteme über endlichen Gruppen zu studieren.Im zweiten Punkt geht es um das gewichtete Paarungsproblem auf dünnen zufälligen Graphen. Der Physiknobelpreisträger Giorgio Parisi und seine co-Autoren haben kürzlich eine bemerkenswert genaue Vermutung zum erwarteten Gewicht einer minimalen perfekten Paarung auf einem zufälligen Graphen formuliert, die wir rigoros untersuchen werden.Im dritten Punkt ist das Ziel, Ideen aus der Physik heranzuziehen, um sehr bekannte, seit langem offene Fragestellungen das Hamiltonkreisproblem in dünne zufälligen Graphen betreffend zu studieren.MethodenWir werden auf der Grundlage von Ideen aus der statistischen Physik neue Techniken für das Studium dünner zufälliger Strukturen entwickeln. Insbesonere zielen wir darauf ab, eine rigorose mathematische Grundlage für heuristische Ansätze wie "Belief Propagation" zu schaffen.OriginalitätIm Gegensatz zu den meisten existierenden Untersuchungen in diesem Bereich fehlen den o.g. Gegenständen dieses Projekts wesentliche Symmetrieeigenschaften. Während beispielsweise aufgrund der inhärenten Symmetrie Hamiltonkreise in zufälligen regulären Graphen leicht nachzuweisen sind, ist dies in irregulären dünnen Zufallsgraphen ein bekanntes offenes Problem.ProjektbeteiligteEs handelt sich um ein gemeinsames FWF-DFG-Projekt, an dem die Kombinatorikgruppe der TU Graz (Prof. Mihyun Kang) und die Effiziente Algorithmen und Komplexitätsgruppe der TU Dortmund (Prof. Amin Coja-Oghlan).

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Österreich
• Kooperationspartnerin: Professorin Dr. Mihyun Kang