CAREER: Understanding the Evolution of Random Graphs with Complex Dependencies: Phase Transition and Beyond

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Time-evolving random networks/random graph processes play an important role in several branches of mathematics and science, including extremal combinatorics, complex networks, and statistical physics. This project seeks to develop new theory for such random graph processes, in order to better understand their properties, improve existing methods of analysis, and rigorously justify their applications. In doing so, the proposed research addresses long-standing open questions in phase transition of dependent random graph processes. The goal of this research is to show that a variety of dependent random graph processes exhibit similar phase transition behavior. Another major thrust of the proposed research is to transfer these new analytical tools from constrained random graph processes to resolve open questions in extremal combinatorics, including Ramsey and Turan type problems. These new mathematical tools can also be used to tackle related problems arising in network science, number theory, computer science, and engineering. The educational component includes annual K-12 math teacher workshops, research opportunities for graduate and undergraduate students,and a multidisciplinary workshop/summer school for junior researchers and undergraduates. The main theme of this project is the development of new theory and applications for time-evolving random graph processes with dependencies (that grow step-by-step according to specific rules or structural constraints). One goal is to establish fundamental phase transition properties such as location/existence of critical points, bounds on the second largest component, and analyticity of scaling limits. A second goal is to justify the universality paradigm, i.e., prove that the phase transition of a range of dependent random graph processes such as the random d-process belong to the same universality class. To this end we will develop a general proof framework which allows us to show, among others, that the largest giant component grows at a linear rate in the supercritical phase. Another goal is to improve/sharpen the analysis of constrained random graph processes such as the H-free process. Here one key ingredient is a more robust analysis framework based on semi-randomization (that works under much weaker technical assumptions), which will allow us to significantly broaden the scope of applications in Ramsey and Turan theory. Each of these goals is related to analytic, combinatorial, and probabilistic properties, and this project focuses on development of new mathematical theory at the intersection of these areas, and will enable us to attack important and challenging questions pertaining to explosive percolation and other well-known and notoriously difficult open problems in the area. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.