From small eigenvalues to large cuts, and Chowla's cosine problem
Vienna Combinatorics Seminar
Abstract:
Consider the eigenvalues of the adjacency matrix of a graph. If the graph is a disjoint union of cliques, the least eigenvalue is 0 or −1. Conversely, what can we say about a graph whose least eigenvalue is small in absolute value? In particular, must such graphs contain a large clique, or even be "close" to a disjoint union of cliques? This question is not only interesting in its own right, but also connected to two seemingly unrelated topics: Chowla's cosine problem (in harmonic analysis) and the maximum cut problem (in graph theory). In this talk, I will discuss our recent result on the eigenvalue question: every graph with average degree d and least eigenvalue |λn|≤dt contains a clique of size d1−O(t). I will present some high-level ideas on how to study the graph structure with help of λn. I will also discuss some backgrounds of Chowla's cosine problem as well as the maximum cut problem, and how our eigenvalue result implies a polynomial improvement on both problems.