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

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

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.