From small eigenvalues to large cuts and Chowla's cosine problem
演讲者
Zhihan Jin
时间
2026年09月22日 17:05 至 18:15
地点
Online
线上
Zoom 787 662 9899
(BIMSA)
摘要
Consider the eigenvalues of the adjacency matrix of a graph. If the graph is a disjoint union of cliques, then the least eigenvalue is 0 or -1. Conversely, what can we say about a graph whose least eigenvalue is small in absolute value? In joint work with Aleksa Milojević, István Tomon and Shengtong Zhang, we prove that every graph with average degree d and least eigenvalue |λn| ≤ d^t contains a clique of size d^{1-O(t)}.
As a consequence, we obtain the first polynomial bound for Chowla’s cosine problem (1965): for every finite set A of natural integers, the minimum of the cosine polynomial satisfies min_x sum_{a \in A} cos(ax) < -|A|^{-0.09}. 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^{0.49} has a cut of size at least m/2 + m^{0.5001}.
As a consequence, we obtain the first polynomial bound for Chowla’s cosine problem (1965): for every finite set A of natural integers, the minimum of the cosine polynomial satisfies min_x sum_{a \in A} cos(ax) < -|A|^{-0.09}. 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^{0.49} has a cut of size at least m/2 + m^{0.5001}.
演讲者介绍
Zhihan Jin is an ISTA Fellow at the Institute of Science and Technology Austria (ISTA). He recently received his PhD in mathematics from ETH Zürich under the supervision of Benny Sudakov. His research interests lie in probabilistic and extremal combinatorics and connections to other areas.