Spectral and Extremal Graph Theory

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

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.