2025/07/14 by Shengtong Zhang, Zhang, Shengtong · 2 citations
Computer Science · #Graph Labeling and Dimension Problems #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2507.10037
For any ε> 0, we show that if G is a regular graph on n ≫ε1 vertices that is ε-far (differs by at least εn2 edges) from any Turán graph, then its second eigenvalue λ2 satisfies λ2 ≥ 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.