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

时间演化随机网络/随机图过程在数学和科学的几个分支中扮演着重要的角色，包括极值组合学、复杂网络和统计物理。这个项目致力于为这种随机图过程发展新的理论，以便更好地理解它们的性质，改进现有的分析方法，并严格证明它们的应用。在这方面，提出的研究解决了相依随机图过程相变中的长期悬而未决的问题。这项研究的目的是证明各种相依随机图过程表现出相似的相变行为。该研究的另一个主要目的是将这些新的分析工具从受约束的随机图过程转移到解决极值组合数学中的公开问题，包括Ramsey和Turan型问题。这些新的数学工具也可以用来解决网络科学、数论、计算机科学和工程学中出现的相关问题。教育部分包括一年一度的K-12数学教师工作坊，为研究生和本科生提供的研究机会，以及为初级研究人员和本科生举办的多学科研讨会/暑期班。该项目的主要主题是开发具有相关性的时间演化随机图过程的新理论和应用(根据特定规则或结构约束逐步增长)。一个目标是建立基本的相变性质，如临界点的位置/存在，第二大分量的界限，以及标度极限的解析性。第二个目标是证明普适性范式，即证明一系列相依随机图过程(如随机d-过程)的相变属于同一普适性类。为此，我们将开发一个通用的证明框架，使我们能够证明，除其他外，最大的巨型成分在超临界阶段以线性速度增长。另一个目标是改进/提高对约束随机图过程(如无H过程)的分析。这里的一个关键因素是基于半随机化的更强大的分析框架(在更弱的技术假设下工作)，这将使我们能够显著扩大Ramsey和Turan理论的应用范围。这些目标中的每一个都与分析、组合和概率性质有关，这个项目专注于在这些领域的交叉点发展新的数学理论，并将使我们能够解决与爆炸渗流和该领域其他众所周知的和臭名昭著的难题有关的重要和具有挑战性的问题。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.