Random graphs: cores, colourings and contagion

随机图：核心、着色和传染

• 批准号: 397269007
• 负责人: Professor Dr. Amin Coja-Oghlan
• 金额: --
• 依托单位: Informatik II - Lehrstuhl Effiziente Algorithmen und Komplexitätstheorie
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/397269007?language=en
• 关键词: Random; graphs; cores; colourings; contagion

Since the pioneering work of Paul Erdos and Alfred Renyi from the middle of the last century the study of random graphs has been a topic of fundamental interest in combinatorics. Random graphs have been used in extremal combinatorics to construct objects with apparently self-contradictory properties as required in Ramsey theory. A very well-known recent contribution of this kind is the work of Bohman and Keevash (2013) on the triangle-free random graph process, which yields a bound on the Ramsey number R(3,k). Other applications emerge in computer science, where random (hyper-)graphs are used as hashing schemes (Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh, Rink 2010) or in the construction of error-correcting codes (e.g. Giurgiu, Macris, Urbanke 2016). Furthermore, random graphs play an important role in the study of complex networks (e.g. van der Hofstad 2016). Despite their importance in combinatorics, computer science and many other disciplines, several important properties of random graphs remain poorly understood. The aim of this project, which is a joint D-A-CH application by Amin Coja-Oghlan of Goethe University Frankfurt and Mihyun Kang of TU Graz, is to make significant progress on several fundamental and (in some cases) long-standing open problems by bringing to bear our joint arsenal of modern mathematical techniques. Concrete topics include the k-core problem in random graphs, which is perhaps the most natural generalisation of the 'giant component' problem studied in the seminal work of Erdos and Renyi, the chromatic number problem, originally posed by Erdos and Renyi in 1960, and the contagion problem of cascading infections.

自上个世纪中期Paul Erdos和Alfred Renyi的开创性工作以来，随机图的研究一直是组合学中的一个基本兴趣话题。随机图已被用于极值组合学中，以构造具有明显自相矛盾性质的对象，如拉姆齐理论所要求的。最近一个非常著名的贡献是Bohman和Keevash（2013）关于无三角随机图过程的工作，它给出了Ramsey数R（3，k）的界。其他应用出现在计算机科学中，其中随机（超）图被用作散列方案（Dietzfelbinger，Goerdt，Mitzenmacher，Montanari，Pagh，Rink 2010）或用于纠错码的构造（例如Giurgiu，Macris，Urbanke 2016）。此外，随机图在复杂网络的研究中发挥着重要作用（例如货车der Hofstad 2016）。 尽管随机图在组合数学、计算机科学和许多其他学科中很重要，但它的一些重要性质仍然知之甚少。该项目的目的是由歌德大学法兰克福的Amin Coja-Oghlan和格拉兹的Mihyun Kang联合提出的D-A-CH应用，旨在通过运用我们的现代数学技术，在几个基本的和（在某些情况下）长期存在的开放问题上取得重大进展。具体的议题包括k-核心问题的随机图，这也许是最自然的概括的“巨人组成部分”问题研究的开创性工作的鄂尔多斯和仁义，色数问题，最初提出的鄂尔多斯和仁义在1960年，和传染问题的级联感染。