Back to Search
Start Over
Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines
- Publication Year :
- 2017
- Publisher :
- arXiv, 2017.
-
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^* := \sqrt{2+\sqrt{5}} \approx 2.058$ and $\lambda \not\in \{\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+\dots+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^*}$. 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 \neq \tfrac{1}{3}, \tfrac{1}{5}, \tfrac{1}{1+2\sqrt{2}}$, which improves a recent result of Balla, Dr\"axler, Keevash and Sudakov.<br />Comment: 23 pages, this version fixes an error in Theorem 1, accepted to Israel J. Math., corrections suggested by the referee have been incorporated
- Subjects :
- Euclidean space
Spectral radius
General Mathematics
010102 general mathematics
52C35, 05C50, 05D10
Metric Geometry (math.MG)
0102 computer and information sciences
Lambda
01 natural sciences
Graph
Combinatorics
Mathematics - Metric Geometry
010201 computation theory & mathematics
Bounded function
FOS: Mathematics
Mathematics - Combinatorics
Asymptotic formula
Combinatorics (math.CO)
0101 mathematics
Equiangular lines
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....31a8b533eb64129de598780c413a23de
- Full Text :
- https://doi.org/10.48550/arxiv.1708.02317