{
  "id": "1708.02317",
  "version": "v1",
  "published": "2017-08-07T21:59:04.000Z",
  "updated": "2017-08-07T21:59:04.000Z",
  "title": "Forbidden subgraphs for graphs of bounded spectral radius, with applications to equiangular lines",
  "authors": [
    "Zilin Jiang",
    "Alexandr Polyanskii"
  ],
  "comment": "15 pages",
  "categories": [
    "math.CO",
    "math.MG"
  ],
  "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 for every $\\lambda < \\lambda^* := \\sqrt{2+\\sqrt{5}} \\approx 2.058$, whereas $\\mathcal{F}(\\lambda)$ cannot for every $\\lambda \\ge \\lambda^*$. 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 $\\mathcal{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 $\\mathcal{R}^n$ with angle $\\arccos\\alpha$. We establish an approach to determine the constant $c$ such that $N_\\alpha(n) = cn + O_\\alpha(1)$ for every $\\alpha > \\frac{1}{1+2\\lambda^*}$. We also show that $N_\\alpha(n) \\le 1.81n + O_\\alpha(1)$ for every $\\alpha \\neq \\tfrac{1}{3}$, which improves a recent result of Balla, Dr\\\"axler, Keevash and Sudakov.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-07T21:59:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C35",
      "05C50",
      "05D10"
    ],
    "keywords": [
      "equiangular lines",
      "bounded spectral radius",
      "applications",
      "dimensional euclidean space",
      "forbidden subgraphs characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}