Random graphs: cores, colourings and 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.