Date:
Mon, 06/12/202115:00-17:00
HUJI Combinatorics Seminar
When: Monday December 6th, 2021, at 3PM (Israel time)
Where: B400 in the CS\Engineering building
Speaker: Igor Balla (TAU)
Title: Equiangular lines and Regular graphs
Abstract:
In 1973, Lemmens and Seidel asked to determine N_alpha(r), the maximum number of equiangular lines in 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 >= Omega(1 / r^1/5).
Our projection method generalizes to complex equiangular lines in C^r, which may be of independent interest in quantum theory. Applying this method also allows us to obtain
When: Monday December 6th, 2021, at 3PM (Israel time)
Where: B400 in the CS\Engineering building
Speaker: Igor Balla (TAU)
Title: Equiangular lines and Regular graphs
Abstract:
In 1973, Lemmens and Seidel asked to determine N_alpha(r), the maximum number of equiangular lines in 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 >= Omega(1 / r^1/5).
Our projection method generalizes to complex equiangular lines in 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 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 r(r+1)/2 equiangular lines in R^r,
- an improvement to Welch's bound in coding theory.