Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines

The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Let $\mathcal{F}(λ)$ be the family of connected graphs of spectral radius $\le λ$. We show that $\mathcal{F}(λ)$ can be defined by a finite set of forbidden subgraphs if and only if $λ< λ^* := \sqrt{2+\sqrt{5}} \approx 2.058$ and $λ\not\in \{α_2, α_3, \dots\}$, where $α_m = β_m^{1/2} + β_m^{-1/2}$ and $β_m$ is the largest root of $x^{m+1}=1+x+\dots+x^{m-1}$. The study of forbidden subgraphs characterization for $\mathcal{F}(λ)$ is motivated by the problem of estimating the maximum cardinality of equiangular lines in the $n$-dimensional Euclidean space $\mathbb{R}^n$ --- a family of lines through the origin such that the angle between any pair of them is the same. Denote by $N_α(n)$ the maximum number of equiangular lines in $\mathbb{R}^n$ with angle $\arccosα$. We establish the asymptotic formula $N_α(n) = c_αn + O_α(1)$ for every $α\ge \frac{1}{1+2λ^*}$. In particular, $N_{1/3}(n) = 2n+O(1)$ and $N_{1/5}(n), N_{1/(1+2\sqrt{2})}(n) = \frac{3}{2}n+O(1)$. Besides we show that $N_α(n) \le 1.49n + O_α(1)$ for every $α\neq \tfrac{1}{3}, \tfrac{1}{5}, \tfrac{1}{1+2\sqrt{2}}$, which improves a recent result of Balla, Dräxler, Keevash and Sudakov.

No reviews yet.

No comments yet.