Spectral graph theory is the study of the relationship between the graphical properties of a graph and the spectral properties (i.e., eigenvalues and eigenvectors) of various matrices associated with that graph, most commonly the adjacency matrix. The spectrum of the adjacency matrix of a cubic graph (i.e., one where each vertex has three neighbours) on \( n \) vertices is a set of \( n \) real numbers lying in the interval \( [-3,3] \) and it determines a surprising amount of information about the graph. A spectral gap set \( X \) is an open subset of \( (-3,3) \) with the property that there are an infinite number of cubic graphs whose spectrum is disjoint from \( X \). For example, the interval \( (-3,-2) \) is a spectral gap set because the infinite family of cubic line graphs has no eigenvalues in \( (-3,-2) \), and in fact the precise list of all cubic graphs whose spectrum avoids \( (-3,-2) \) is known. Krystal Guo and Bojan Mohar showed that the interval \( (-1,1) \) is a spectral gap set for cubic graphs, and recently Alicia Kollár and Peter Sarnak demonstrated the same result for \( (-2,0) \) and in addition, showed that any spectral gap interval has length at most \( 2 \). In this talk I describe some recent work, joint with Krystal Guo, where we give exact characterisations of the cubic graphs with spectra avoiding \( (-1,1) \) and those with spectra avoiding \( (-2,0) \). These exact characterisations allow us to deduce that \( (-1,1) \) is a maximal spectral gap set, thereby answering a question of Kollár and Sarnak. The talk is largely non-technical and should be accessible to anyone familiar with basic graph theory and linear algebra.
|