From small eigenvalues to large cuts, and Chowla's cosine problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909870588952576 |
|---|---|
| author | Jin, Zhihan Milojević, Aleksa Tomon, István Zhang, Shengtong |
| author_facet | Jin, Zhihan Milojević, Aleksa Tomon, István Zhang, Shengtong |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_03490 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | From small eigenvalues to large cuts, and Chowla's cosine problem Jin, Zhihan Milojević, Aleksa Tomon, István Zhang, Shengtong Combinatorics Classical Analysis and ODEs Number Theory Spectral Theory 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$. |
| title | From small eigenvalues to large cuts, and Chowla's cosine problem |
| topic | Combinatorics Classical Analysis and ODEs Number Theory Spectral Theory |
| url | https://arxiv.org/abs/2509.03490 |