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

Let G be a graph on n vertices, and let λₙ denote the smallest eigenvalue of its adjacency matrix. What can we say about G if |λₙ| is small? Earlier results provided a structure theorem only when |λₙ| was bounded by a polylogarithm in n. In this work, we show that even a mild polynomial bound on |λₙ| 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 Kr-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.

For information about the Richard P. Stanley Seminar in Combinatorics, visit https://math.mit.edu/combin/