From small eigenvalues to large cuts, and Chowla’s cosine problem

Let G be a graph on n vertices, and let λ_n denote the
smallest eigenvalue of its adjacency matrix. What can we say about G
if |λ_n| is small? Earlier results provided a structure theorem only
when |λ_n| was bounded by a polylogarithm in n. In this work, we show
that even a mild polynomial bound on |λ_n| already forces G to have
strong structural properties, essentially resembling a union of
cliques.

As applications, we obtain the first polynomial bound for Chowla’s
cosine problem in harmonic analysis (concurrently with a different
proof by Benjamin Bedert), and establish the first uniformly
polynomial improvement toward the Alon–Bollobás–Krivelevich–Sudakov
conjecture on the maximum cut in K_r-free graphs. Our methods combine
new linear-algebraic techniques, including subspace compressions and
Hadamard products of matrices.

Joint work with Zhihan Jin, Aleksa Milojević, and István Tomon.