Aleksa Milojević

We give a simple proof of the recent remarkable exponential improvement for Ramsey lower bounds, obtained by Ma, Shen and Xie. Our key ingredient is an alternative construction based on Gaussian random graphs, which allows us to simplify their analysis significantly. As a consequence of this simpler analysis, we also obtain better quantitative bounds.

We show that there exists an absolute constant \(\gamma > 0\) such that for every \(A \subseteq \mathbb{Z}_{>0}\) we have \[ \min_{x \in [0,2\pi]} \sum_{a \in A} \cos(ax) \leq -\Omega(|A|^\gamma). \] This gives the first polynomial bound for Chowla's cosine problem from 1965. To show this, we prove structural statements about graphs whose smallest eigenvalue is small in absolute value. As another application, we show that any graph \(G\) with \(m\) edges and no clique of size \(m^{1/2-\delta}\) has a cut of size at least \(m/2 + m^{1/2+\varepsilon}\) for some \(\varepsilon = \varepsilon(\delta) > 0\). This proves a weak version of a celebrated conjecture of Alon, Bollobás, Krivelevich, and Sudakov. Our proofs are based on novel spectral and linear algebraic techniques, involving subspace compressions and Hadamard products of matrices.