





















We prove that every graph with average degree $d$ and smallest adjacency eigenvalue $|λ_n|\leq d^γ$ contains a clique of size $d^{1-O(γ)}$. 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 $$\min_{x\in [0, 2π]}\sum_{a\in A}\cos(ax)\leq -|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-δ}$ has a cut of size at least $m/2+m^{1/2+\varepsilon}$ for some $\varepsilon=\varepsilon(δ)>0$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。