Spectral and Extremal Graph Theory

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

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.