Randomly perturbed graphs: Problems between random and extremal graph theory

• Applicant: Dr. Olaf Parczyk
• Subject Area: Mathematics
• Term: from 2019 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 422062814

In mathematics, the exchange of ideas and methods between different areas often provides interesting new insights and leads to progress in the field. This project is located in discrete mathematics connecting random and extremal graph theory. Random graph theory is concerned with the analysis and properties of typical large graphs. In extremal graph theory rare rigid events forced by specific constraints and maximisation are studied extensively. In between these two, there is the model of randomly perturbed graphs, which is the union of a sparse random and a dense deterministic graph. This fascinating interplay of chaos and order features very interesting phenomena and contributes to our understanding of the behaviour of discrete structures. The focus of this project is on problems in this newly emerged model, which is currently attracting a lot of attention. There is a wide range of possibilities for interpolation between the purely random and the purely deterministic setup, which provides room for new challenging conjectures. Most of the questions ask for embeddings of spanning structures, such as Hamilton cycles, factors of graphs, trees, or general bounded degree graphs. These problems can be approached using a combination of methods from both areas with additional new techniques tailored towards the environment. Ultimately, advances in this perturbed model also promise progress in open questions in the pure setups.

• DFG Programme: Research Fellowships
• International Connection: United Kingdom
• Hosts: Peter Allen, Ph.D.; Professorin Dr. Julia Böttcher; Professor Jozef Skokan, Ph.D.