BIMSA >
Research seminar in Discrete Mathematics
Research seminar in Discrete Mathematics
From small eigenvalues to large cuts and Chowla's cosine problem
From small eigenvalues to large cuts and Chowla's cosine problem
Speaker
Zhihan Jin
Time
Tuesday, September 22, 2026 5:05 PM - 6:15 PM
Venue
Online
Online
Zoom 787 662 9899
(BIMSA)
Abstract
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}.
Speaker Intro
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.