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将集中于极端图理论，该理论试图量化图在变大时必须具有的组合属性（其中大小可以通过几个图参数定义，每个图都提供了一个有趣的理论）。该项目有两个主要推力。首先研究古典Turan和Ramsey理论，这是组合学的两个中心领域。其次研究光谱图理论中的极端问题，其中人们使用线性代数通过矩阵推断该图的组合特性。这些问题是图理论中的基本问题，此外还具有有限的几何形状，组合数理论，组合矩阵理论和理论计算机科学的应用。该项目还将特别关注为学生研究提供建议。该项目将首先在极端图理论中尝试两个臭名昭著的困难问题：查找图形的构造，这些构造证明了两分之一的Turan数字的下限，并找到了Ramsey图的结构。 PI将开发将代数和几何对象与概率方法相结合的最新趋势，以在这两个困难领域取得进展。其次，该项目将尝试在光谱图理论中解决一些长期的猜想，例如图形的光谱差距，Nordhaus-Gaddum型问题以及Turan型问题的光谱版本。此外，将使用图理论方法探讨离散几何形状和组合数理论中的应用。本奖反映了NSF的法定任务，并使用基金会的知识分子优点和更广泛的影响审查标准，认为值得通过评估来获得支持。