An Alon-Boppana--type bound for very dense graphs, with applications to max-cut

For any $ε> 0$, we show that if G is a regular graph on n _ε1 vertices that is $ε$-far (differs by at least εn² edges) from any Turán graph, then its second eigenvalue λ₂ satisfies λ₂ ≥ n1/4 - ε. The exponent $1/4$ is optimal. Our result generalizes an analogous bound, independently obtained by Balla, Räty -- Sudakov-Tomon, and Ihringer, which only applies to graphs with density at most 1/2. Up to a lower-order factor, this confirms a conjecture of Räty, Sudakov and Tomon. Our spectral approach has interesting applications to max-cut. First, we show that if a graph G, on n _ε1 vertices and m edges, is $ε$-far from a disjoint union of cliques, then it has a max-cut of size at least m/2 + n1.01. Our result improves upon a classical result of Edwards by a non-trivial polynomial factor, making progress towards another conjecture of Räty, Sudakov and Tomon. As another application of our method, we show that if a graph G is H-free and has m edges, then G has a max-cut of size at least m/2 + cH m0.5001 where cH > 0 is some constant depending on H only. This result makes progress towards a conjecture of Alon, Bollobás, Krivelevich and Sudakov, and answers recent questions by Glock-Janzer-Sudakov and Balla-Janzer-Sudakov.