The Interplay between Spectral and Combinatorial Properties of Graphs and Association Schemes

图论是分析网络结构和功能的基本理论。通常，这种网络的规模如此之大，以至于用蛮力分析它们的结构是不可行的。挑战在于如何使用能够有效捕捉网络形状的参数。谱图理论是研究图的结构性质的重要工具，与计算机科学和网络设计有着密切的联系。虽然特征值一般不能确定一个图，但它们包含重要的结构信息，在某些情况下，这些信息不能通过任何其他方法获得。结合方案是一种具有高度正则性的组合和代数结构，它位于代数组合学的核心，在编码理论、几何和量子计算中有着重要的应用。在这个项目中，我们将研究图和结合方案的谱性质和组合性质之间的密切联系。该项目将涉及特拉华大学的研究生和本科生。这个项目包含了关于组合和谱问题的谱图理论和涉及单纯Rook图、Wenger图和友谊图的猜想的最新进展，以及通过回答Brouwer关于强正则图和距离正则图及其子成分的连通性的问题而在结合方案理论方面的最新进展。该项目将调查Haemers的猜想，即几乎所有的图都由它们的谱决定，Godsil和Brouwer关于结合方案中图的边和点连通性的猜想，以及相关问题，如理解由有限域上的方程组定义的图的谱和等周性质，或在其他组合问题中出现的图。

Graph theory is essential for analyzing the structure and function of networks. Often the sizes of such networks are so large that analyzing their structures by brute force is not feasible. The challenge is to use parameters that can efficiently capture the shapes of networks. Spectral graph theory provides important tools for studying structural properties of graphs and has close connections to computer science and network design. Although the eigenvalues do not determine a graph in general, they contain important structural information that in some situations, could not be obtained by any other means. Association schemes are combinatorial and algebraic structures with high degree of regularity that sit at the core of algebraic combinatorics and have important applications in coding theory, geometry and quantum computing. In this project, the close connections between the spectral and combinatorial properties of graphs and association schemes will be investigated. This project will involve graduate and undergraduate students at University of Delaware. This project encompasses recent progress in spectral graph theory on combinatorial and spectral problems and conjectures involving simplicial rook graphs, Wenger graphs and friendship graphs as well as in the theory of association schemes by answering questions of Brouwer regarding the connectivity of strongly regular and distance-regular graphs and their subconstituents. The project will investigate conjectures of Haemers that almost all graphs are determined by their spectrum, of Godsil and Brouwer regarding the edge- and vertex-connectivity of graphs in association schemes as well as related problems such as understanding the spectral and isoperimetric properties of graphs defined by systems of equations over finite fields or graphs arising in other combinatorial problems.