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

Abstract

The spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Let $\mathcal{F}(\lambda )$ be the family of connected graphs of spectral radius $\le \lambda$. We show that $\mathcal{F}(\lambda )$ can be defined by a finite set of forbidden subgraphs if and only if $\lambda <{\lambda }^{\ast }:=\sqrt{2+\sqrt{5}}\approx 2.058$ and $\lambda \notin \{{\alpha }_2,{\alpha }_3,\dots \}$, where ${\alpha }_m={\beta }_m^{1/2}+{\beta }_m^{-1/2}$ and ${\beta }_m$ is the largest root of $x^{m+1}=1+x+\cdots +x^{m-1}$. The study of forbidden subgraphs characterization for $\mathcal{F}(\lambda )$ 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_{\alpha }(n)$ the maximum number of equiangular lines in ${\mathbb{R}}^n$ with angle $\arccos \alpha$. We establish the asymptotic formula $N_{\alpha }(n)=c_{\alpha }n+O_{\alpha }(1)$ for every $\alpha \ge \frac{1}{1+2{\lambda }^{\ast }}$. 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_{\alpha }(n)\le 1.49n+O_{\alpha }(1)$ for every $\alpha \ne \frac{1}{3},\frac{1}{5},\frac{1}{1+2\sqrt{2}}$, which improves a recent result of Balla, Dräxler, Keevash and Sudakov.

23 pages, this version fixes an error in Theorem 1, accepted to Israel J. Math., corrections suggested by the referee have been incorporated

References in corpus (2)

• Equiangular lines in Euclidean spaces
• On spectral radii of unraveled balls

Cited by in corpus (8)

• Equiangular lines with a fixed angle
• Spherical two-distance sets and eigenvalues of signed graphs
• Real equiangular lines in dimension 18 and the Jacobi identity for complementary subgraphs
• Bounds for the sum of distances of spherical sets of small size
• Forbidden induced subgraphs for graphs and signed graphs with eigenvalues bounded from below
• p-adic Welch Bounds and p-adic Zauner Conjecture
• On symmetric hollow integer matrices with eigenvalues bounded from below
• Alon-Boppana-type bounds for weighted graphs