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

University Of Delaware, Newark DE

Investigators

Abstract

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.