Paper detail

Gap sets for the spectra of regular graphs with minimum spectral gap

Following recent work by Kollár and Sarnak, we study gaps in the spectra of large connected cubic and quartic graphs with minimum spectral gap. We focus on two sequences of graphs, denoted $Δ_n$ and $Γ_n$ which are more `symmetric' compared to the other graphs in these two families, respectively. We prove that $(1,\sqrt{5}]$ is a gap interval for $Δ_n$, and $[(-1+\sqrt{17})/2,3]$ is a gap interval for $Γ_n$. We conjecture that these two are indeed maximal gap intervals. As a by-product, we show that the eigenvalues of $Δ_n$ lying in the interval $[-3,-\sqrt{5}]$ (in particular, its minimum eigenvalue) converge to $(1-\sqrt{33})/2$ and the eigenvalues of $Γ_n$ lying in the interval $[-4,-(1+\sqrt{17})/2]$ (and in particular, its minimum eigenvalue) converge to $1-\sqrt{13}$ as $n$ tends to infinity. The proofs of the above results heavily depend on the following property which can be of independent interest: with few exceptions, all the eigenvalues of connected cubic and quartic graphs with minimum spectral gap are simple.