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

We prove that every graph with average degree $d$ and smallest adjacency eigenvalue $\mathrm{\mid }{\lambda }_n\mathrm{\mid }\le d^{\gamma }$ contains a clique of size $d^{1-O(\gamma )}$. 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\pi ]}{\min }\sum _{a\in A}\cos (ax)\le -\mathrm{\mid }A{\mathrm{\mid }}^{1\mathrm{/}10-o(1)}\mathrm{.}$$ 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\mathrm{/}2-\delta }$ has a cut of size at least $m\mathrm{/}2+m^{1\mathrm{/}2+\epsilon }$ for some $\epsilon =\epsilon (\delta )>0$.