Zufällig veränderte Graphen: Probleme zwischen zufälliger und extremaler Graphentheorie
Zusammenfassung der Projektergebnisse
Das Thema dieses Projektes war das Modell der zufällig veränderten Graphen. Dieses Modell ist die Vereinigung eines deterministischen Graphen mit einem zufälligen Graphen und verflechtet extremale und probabilistische Graphentheorie. Das Hauptaugenmerk diese Projektes lag auf dem Finden von (aufspannenden) Strukturen, wie Hamiltonkreise, Faktoren von Graphen, Bäumen und beliebige gradbeschränkte Graphen. Während des Projektes haben wir den letzten offenen Fall für Dreiecksfaktoren gelöst, welcher den probabilisitischen Schwellenwert betrifft für einen deterministische Graphen auf n Knoten mit Minimalgrad n/3. Tatsächlich beweisen wir ein viel allgemeineres Ergebnis für Familien von Dreiecken, welches auch ein Stabilitätsresultat beinhaltet. Ähnlich bestimmen wir das gesamte Spektrum für das Quadrat vom Hamiltonkreis und beobachten ein interessantes Verhalten des perturbieren Schwellenwertes mit abzahlbar vielen Sprüngen wenn wir uns dem rein zufälligen Graphen annähern. Dies vervollständigt auch das Bild für Universalität von Graphen mit Maximalgrad zwei. Zwei weitere Arbeiten beschäftigen sich mit dünneren Ausgangsgraphen und positionellen Spielen in dem perturbierten Modell. Weitere Beiträge dieses Projektes beschäftigen sich mit size-Ramsey-Zahlen von Hamiltonkreisen in Hypergraphen, Robustheit von Hamiltonkreisen in zufälligen Hypergraphen, anti-Ramsey-Schwellenwerten für Kreise und Gruppentests.
Projektbezogene Publikationen (Auswahl)
-
Anti-Ramsey threshold of cycles, Discrete Applied Mathematics (2021)
G. F. Barros, B. P. Cavalar, G. O. Mota, and O. Parczyk
-
Maker-Breaker Games on Randomly Perturbed Graphs, SIAM Journal on Discrete Mathematics 35 (2021), no 4, 2734–2748
D. Clemens, F. Hamann, Y. Mogge, and O. Parczyk
-
Random perturbation of sparse graphs, The Electronic Journal of Combinatorics 2 (2021), P2.26
M. Hahn-Klimroth, G. S. Maesaka, Y. Mogge, S. Mohr, and O. Parczyk
-
The size-Ramsey number of 3-uniform tight paths, Advances in Combinatorics, 5 (2021), 12 pp.
J. Han, Y. Kohayakawa, S. Letzter, G. O. Mota, and O. Parczyk
