Graphs with high second eigenvalue multiplicity

Jiang, Tidor, Yao, Zhang, and Zhao recently showed that connected bounded degree graphs have sublinear second eigenvalue multiplicity (always referring to the adjacency matrix). This result was a key step in the solution to the problem of equiangular lines with fixed angles. It led to the natural question: what is the maximum second eigenvalue multiplicity of a connected bounded degree n$n$-vertex graph? The best-known upper bound is O(n/loglogn)$O(n/\log \log n)$. The previously known best-known lower bound is on the order of n1/3$n<^>{1/3}$ (for infinitely many n$n$), coming from Cayley graphs on PSL(2,q)$\operatorname{PSL}(2,q)$. Here we give a construction showing a lower bound of n/log2n$\sqrt {n/\log _2 n}$. We also construct Cayley graphs with second eigenvalue multiplicity at least n2/5-1$n<^>{2/5}-1$. Earlier techniques show that there are at most O(n/loglogn)$O(n/\log \log n)$ eigenvalues (counting multiplicities) within O(1/logn)$O(1/\log n)$ of the second eigenvalue. We give a construction showing this upper bound on approximate second eigenvalue multiplicity is tight up to a constant factor. This demonstrates a barrier to earlier techniques for upper bounding eigenvalue multiplicities.