Randomly perturbed graphs: Problems between random and extremal graph theory

在数学中，不同领域之间思想和方法的交流经常提供有趣的新见解，并导致该领域的进步。本课题位于离散数学中，连接随机图论和极值图论。随机图论是研究典型大图的分析和性质的理论。在极值图论中，对特定约束和极值约束下的稀有刚性事件进行了广泛的研究。在这两者之间，有一种随机摄动图模型，它是稀疏随机图和密集确定性图的结合。这种混沌和有序的相互作用具有非常有趣的现象，有助于我们理解离散结构的行为。这个项目的重点是这个新出现的模型中存在的问题，这个问题目前引起了很多关注。在纯随机和纯确定性设置之间存在广泛的插值可能性，这为新的具有挑战性的猜想提供了空间。大多数问题都是关于生成结构的嵌入，比如Hamilton循环，图的因子，树，或者一般的有界度图。这些问题可以结合这两个领域的方法和针对环境量身定制的额外新技术来解决。最终，这种扰动模型的进步也有望在纯设置的开放问题上取得进展。

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.