Spanning Structures in Random Graphs

随机图是由与概率分布相关联的随机机制生成的典型大尺寸的图。它们为大型复杂网络(如电信网络、社交网络、互联网和神经网络)提供简化的抽象模型，对于这些网络，明确的确定性描述通常是不切实际的或不可用的。近年来，由于这类网络的无处不在的扩散以及对其分析的理论框架的需要，人们对这一主题的兴趣有所增长。图的许多基本性质可以用它们的生成子结构来表示，例如生成树、哈密尔顿圈和完美匹配。这种结构是图论的精髓，在计算机科学、组合优化和统计物理等其他领域发挥着核心作用。这项研究项目旨在通过解决该领域的基本开放问题来扩展对随机图的几个模型中的跨度结构的数学理解。此外，这个项目为研究生提供了研究培训的机会。随机图中的生成结构的分析是概率组合数学中一个有着悠久传统的中心主题。然而，对于经典的ERDőS-Rényi图的许多基本问题对于其他随机图的基本模型仍然是开放的。研究人员计划解决几个随机图模型中有关跨越结构(及其彩虹对应结构)的存在、出现和填充的一些未决问题，这些模型包括随机几何图、优先连接图和随机提升。这些模型的约束性质使得它们的分析与ERDőS-Rényi图的分析显著不同(而且往往比它更具挑战性)。为了克服这些障碍，这项研究结合了几何、概率和组合成分的新方法。该项目由组合数学计划和既定的刺激竞争研究计划(EPSCoR)联合资助。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Random graphs are graphs of typically large size generated by a random mechanism associated to a probability distribution. They provide simplified abstract models for large complex networks — such as telecommunication networks, social networks, the Internet, and neural networks — for which an explicit deterministic description is often impractical or not available. Interest in the subject has grown in recent years due to the ubiquitous proliferation of such networks and the need of a theoretical framework for their analysis. Many fundamental properties of graphs can be formulated in terms of their spanning substructures — such as spanning trees, Hamilton cycles and perfect matchings. Such structures are quintessential in graph theory and play a central role in other fields such as computer science, combinatorial optimization, and statistical physics. This research project aims to extend mathematical understanding of spanning structures in several models of random graphs by addressing fundamental open questions in the field. In addition, this project provides research training opportunities for graduate students.The analysis of spanning structures in random graphs is a central theme with a long tradition in probabilistic combinatorics. However, many basic questions that are well understood for the classical Erdős-Rényi graphs remain wide open for other fundamental models of random graphs. The investigator plans to settle some of these open questions concerning the existence, emergence, and packing of spanning structures (and their rainbow counterparts) in several models of random graphs, including random geometric graphs, preferential attachment graphs, and random lifts. The constrained nature of these models makes their analysis significantly different from (and often more challenging than) that of Erdős-Rényi graphs. To overcome these obstacles, the research incorporates novel approaches that combine geometric, probabilistic, and combinatorial ingredients.This project is jointly funded by the Combinatorics program and the Established Program to Stimulate Competitive Research (EPSCoR).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.