Spanning Structures in Random Graphs

随机图中的跨越结构

• 批准号: 2201590
• 负责人: Xavier Perez Gimenez
• 金额: $ 22.49万
• 依托单位: University of Nebraska-Lincoln
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-01 至 2025-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2201590&HistoricalAwards=false
• 关键词: Spanning; Structures; Random; Graphs

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.

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