Phase transitions and critical phenomena in random graphs

The theory of random graphs is one of the most important subjects in discrete mathematics, and the intense study of random graphs has brought together different fields such as discrete mathematics, probability theory, theoretical computer science, and statistical physics. The proposed project will focus on random graph processes and random hypergraphs. The constraints imposed on these random graph models (in particular random graph processes) lead to difficulties in the analysis of their asymptotic behaviour, due to the long-term and/or global dependence between edges. To overcome these difficulties, new approaches have to be found. The main objective of the proposed project is to advance analytic and probabilistic approaches and to apply them to analyse asymptotic behaviour of such complex random graph models. The scientific program of the proposed project consists of two main themes, which are closely related in that both themes deal with phase transitions and critical phenomena. (1) Random graph processes -- Development of general analytic approach to study the phase transition -- Critical phenomena and component-size distribution (2) Random hypergraph graphs -- Component-exploration approaches by breath-first search and depth-first search -- Applications to random hypergraphs, in particular in supercritical regime. First, the proposed project aims to investigate random graph processes based on the paradigm of the power of multiple choices. Instead of standard probabilistic approaches and ordinary differential equations method, we will develop a general analytic approach based on the method of characteristics to find and analyze solutions of quasi-linear partial differential equations and to understand the local properties of solutions. We will apply this analytic approach to study the detailed behaviour of random graphs, in which a random selection out of multiple choices is sequentially made, e.g. the product rule suggested by Bollobas. The proposed project is of fundamental nature since only certain cases and properties of considered random graph models have been understood by the time, and a general analytic approach and a comprehensive analysis of more difficult random graph models does not exist until now. Second, this project plans to advance two component-exploration approaches for the analysis of supercritical random graphs: one approach is based on the breath-first search and its dual process (recently improved by Bollobas and Riordan) and the other one on the depth-first search (a recent approach of Krivelevich and Sudakov). Both approaches are so far used only in the analysis of the classical Erdos and Renyi random graphs, but provide simple and short proofs. We will advance these approaches and apply them to supercritical random hypergraphs, which are as of yet not very well understood. It will require more advanced tools, in particular from the branching process theory and the martingale theory.

The scientific goal of the project was to investigate random graph processes and random hypergraphs, by advancing analytic and probabilistic approaches and applying them to analyse asymptotic behaviour of such random graph models. The whole project has been successfully carried out and the scientific goals of the project are achieved. The significant achievements of the project are fivefold: (1) we have successfully accomplished the scientific goals set for the project; (2) the research results obtained through the project have been published or submitted for publication in leading peer-reviewed journals or peer-reviewed conference proceedings- 20 papers in total; (3) the significant results are disseminated also in important international scientific conferences; (4) the scientific results of the project have led to one PhD thesis; (5) on top of these scholarly achievements, the additional gain of the project is that the project leader and her team members have strengthened the existing collaborations and have successfully expanded new collaborations with leading experts. The most significant scientific results of the project include (a) giant high-order component in random hypergraphs; (b) critical threshold probability for jigsaw percolation on random hypergraphs; (c) phase transition in bootstrap processes on inhomogeneous random graphs; (d) description of how the k-core is embedded into random graphs. Since its foundation five decades ago, the theory of random graphs has found its way into other sciences as a rich source of models describing fundamental aspects of a broad range of complex structures and phenomena, arising everywhere from nature to society (e.g. life sciences, man-made networks, social sciences, the brain).