Random Graphs: Cores, Colourings and Contagion

Graphs are mathematical models of networks occurring in the sciences, economics or informatics. Frequently the evolution of networks can be modelled probabilistically, which motivates the study of random graphs. Also it has emerged that random graphs are extremely rich and useful mathematical objects with numerous applications in other areas of mathematics such as information theory or Ramsey theory. The systematic study of random graphs started in the 1960s with the work of the Hungarian mathematicians Paul Erdos and Alfred Renyi. Yet to this day many important properties of random graphs remain poorly understood. The aim of this collaborative project, which is hosted jointly at Goethe University Frankfurt in Germany and at TU Graz in Austria, is to advance the rigorous mathematical understanding of random graphs with the assistance of novel mathematical tools originating, for example, from enumerative combinatorics or the recent theory of graph limits. Specific problems that we intend to study include the graph colouring problem on random graphs, strongly connected sub-structures of random graphs called cores and the contagion of cascading events. For example, graph colouring has been a core topic of mathematics since the famous four colour problem posed by Gutherie in 1852. Cores have applications, for example, in coding theory, and contagion is a key topic in the study of complex social or artificial networks.

The overarching topic of the research project is the theory of random graphs. This exciting area at the junction of combinatorics and probability theory was initiated by Erds and Rényi in the 1960s. Random graphs have since an impact on a broad range of other disciplines, including computer science, statistics, statistical physics and network science. In this project we made progress on important open problems on cores, colourings, and contagion. Cores. The seminal result in random graph theory that established the area as a whole was the work of Erds and Rényi on the evolution of the connected components of random graphs. Cores are natural generalisations of connected components. In this project we studied core-structures arising from a sparse parity matrix. An important ingredient to the proof of this result is the analysis of the Warning Propagation message passing algorithm, a ubiquitous combinatorial message passing algorithm of pivotal importance to the physics view on random combinatorial structures. Colourings. Graph colouring is one of the best-known and perhaps also one of the most appealing problems in combinatorics. The chromatic number of a graph is the least number of colours that are needed to colour the graph. The problem of finding the chromatic number of random graphs is one of the longest-standing open problems in random graph theory. In this project we made progress on this fundamental combinatorial problem. We generalised Bollobs' classical result on the asymptotics of the chromatic number of the binomial random graph to the stochastic block model and to graphons. Contagion. The challenges associated with modelling the coronavirus pandemic demonstrate the pivotal importance of understanding contagion processes on networks. In this project we studied the majority dynamics on random graphs, which is related to contagion processes on random graph models. We resolved a conjecture on majority dynamics on the Erds-Rényi random graph, which was posed in the year 2016 by Benjamini et al. We were informed by the journal Random Structures & Algorithms that this paper is among the top 10 most downloaded papers in the journal published in the years 2019-2020. We do not see any immediate effects of the project beyond the scientific/scholarly field, because the project dealt with fundamental/theoretical mathematics problems. However, there might be applications to other fields, such as social networks and epidemics on networks.