Spectral and Extremal Graph Theory

谱与极值图论

• 批准号: 2245556
• 负责人: Michael Tait
• 金额: $ 21万
• 依托单位: Villanova University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2245556&HistoricalAwards=false
• 关键词: Spectral; Extremal; Graph; Theory

This project is in graph theory, where properties and structures of a network are explored. The PI will focus on extremal graph theory which attempts to quantify what combinatorial properties a graph must have when it gets large (where size can be defined by several graph parameters, each giving an interesting theory). The project has two main thrusts. First to study classical Turan and Ramsey theory, two central areas in combinatorics. And second to study extremal problems in spectral graph theory, where one uses linear algebra to deduce combinatorial properties of the graph via matrices. These problems are fundamental ones in graph theory and additionally have applications to finite geometry, combinatorial number theory, combinatorial matrix theory, and theoretical computer science. The project will will also have a specific focus on advising student research. The project will first attempt two notoriously difficult problems in extremal graph theory: finding constructions of graphs certifying lower bounds for bipartite Turan numbers and finding constructions of Ramsey graphs. The PI will develop the recent trend of combining algebraic and geometric objects with probabilistic methods to make progress on these two difficult areas. Second, the project will attempt to solve several long-standing conjectures in spectral graph theory regarding for example spectral gaps of graphs, Nordhaus-Gaddum type problems, and spectral versions of Turan-type problems. Additionally, applications in discrete geometry and combinatorial number theory will be explored using graph theoretic methods.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.

该项目属于图论领域，探索网络的属性和结构。 PI 将重点关注极值图论，该理论试图量化图变大时必须具有的组合属性（其中大小可以由多个图参数定义，每个参数都给出一个有趣的理论）。该项目有两个主要目标。首先研究经典图兰和拉姆齐理论，组合数学的两个核心领域。其次是研究谱图论中的极值问题，其中使用线性代数通过矩阵推导图的组合属性。这些问题是图论中的基本问题，并且还应用于有限几何、组合数论、组合矩阵论和理论计算机科学。该项目还将特别关注为学生研究提供建议。该项目将首先尝试极值图论中的两个众所周知的难题：寻找证明二分图兰数下界的图的构造和寻找拉姆齐图的构造。 PI将发展将代数和几何对象与概率方法相结合的最新趋势，以在这两个困难领域取得进展。其次，该项目将尝试解决谱图理论中几个长期存在的猜想，例如图的谱间隙、Nordhaus-Gaddum 型问题和 Turan 型问题的谱版本。此外，还将使用图论方法探索离散几何和组合数论中的应用。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。