Randomly perturbed graphs: Problems between random and extremal graph theory
Final Report Abstract
The topic of this project was the model of randomly perturbed graphs. This is the union of a dense deterministic graph with a sparse random graph and intertwines probabilistic and extremal graph theory. The main focus was on embedding of (spanning) structures, such as Hamilton cycles, factors of graphs, trees, or general bounded degree graphs. During the project we resolved the last open case for the triangle-factor, which was to determine the probability threshold when the deterministic graph has n vertices and minimum degree n 3. In fact, we are able to prove a much more general result for families of triangles that also includes a stability statement. Similarly we fully resolve the picture for the square of the Hamilton cycle, where the perturbed threshold shows an interesting behaviour with countably many jumps when tending towards the purely random model. This also closes the range for universality of graphs with maximum degree two. Two more papers are concerned with slightly sparser host graphs and positional games in the perturbed setup. Other contributions of this project are on size-Ramsey numbers of tight Hamilton cycles in hypergraphs, resilience for tight Hamiltonicity in random hypergraphs, anti-Ramsey thresholds for cycles, and sparsity-constrained group testing.
Publications
- Anti-Ramsey threshold of cycles, Discrete Applied Mathematics (2021)
G. F. Barros, B. P. Cavalar, G. O. Mota, and O. Parczyk
(See online at https://doi.org/10.1016/j.dam.2021.10.021) - 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
(See online at https://doi.org/10.1137/20M1385044) - 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
(See online at https://doi.org/10.37236/9510) - 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
(See online at https://doi.org/10.19086/aic.24581)
