TAU Combinatorics Seminar 2021/22

When: Sunday, November 28, 10am
Where: Schreiber 309
Speaker: Igor Balla, Tel Aviv University
Title: Equiangular lines and regular graphs


In 1973, Lemmens and Seidel asked to determine $N_{\alpha}(r)$, the maximum number of equiangular lines in $\mathbb{R}^r$ with common angle $\arccos(\alpha)$. Recently, this problem has been almost completely settled when $r$ is exponentially large relative to $1/\alpha$, with the approach both relying on Ramsey's theorem, as well as being limited by it. In this talk, we will show how orthogonal projections of matrices with respect to the Frobenius inner product can be used to overcome this limitation, thereby obtaining significantly improved upper bounds on $N_{\alpha}(r)$ when $r$ is polynomial in $1/\alpha$. In particular, our results imply that $N_{\alpha}(r) = \Theta(r)$ for $\alpha\ge \Omega(1/r^{1/5})$.

Our projection method generalizes to complex equiangular lines in $\mathbb{C}^r$, which may be of independent interest in quantum theory. Applying this method also allows us to obtain

  • the first universal bound on the maximum number of complex equiangular lines in $\mathbb{C}^r$ with common Hermitian angle $\arccos(\alpha)$,
  • an extension of the Alon-Boppana theorem to dense regular graphs, which is tight for strongly regular graphs corresponding to $\binom{r+1}{2}$ equiangular lines in $\mathbb{R} ^r$,
  • an improvement to Welch's bound in coding theory.