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

Abstract

We prove that every graph with average degree $d$ and smallest adjacency eigenvalue $|\hat{I}{»}_n|\le d^3$ contains a clique of size $d^{1-O({\hat{I}}^3)}$. A simple corollary of this yields the first polynomial bound for Chowla's cosine problem (1965): for every finite set $A\subseteq {\mathbb{Z}}_{>0}$, the minimum of the cosine polynomial satisfies $$\underset{x\in [0,2\ddot{I}€]}{\min }\sum _{a\in A}\cos (ax)\le -|A{|}^{1/10-o(1)}.$$ Another application makes significant progress on the problem of MaxCut in $H$-free graphs initiated by Erdős and Lovász in the 1970's. We show that every $m$-edge graph with no clique of size $m^{1/2-\hat{I}´}$ has a cut of size at least $m/2+m^{1/2+\epsilon }$ for some $\epsilon =\epsilon (\hat{I}´)>0$.

Improved presentation and constants. 49 pages This combines and replaces the manuscripts arXiv:2507.10037 and arxiv:2507.13298 (which will not be published), with additional results and improvements