权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

职业：理解具有复杂依赖性的随机图的演化：相变及其他

基本信息

批准号：
2225631
负责人：
Lutz Warnke
金额：
$ 40.43万
依托单位：
University of California-San Diego
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-06-01 至 2025-04-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2225631&HistoricalAwards=false
关键词：
CAREER Understanding Evolution Random Graphs

项目摘要

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.

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