What type of study is this?

This is a Quantitative Study study.

October 2, 2025Open Access

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

Key Points

The second eigenvalue of a regular graph far from any Turán graph is bounded, enhancing understanding of spectral properties.
A new max-cut result provides that if a graph is ε-far from cliques, the max-cut size is at least half the edges plus a polynomial factor.
The results also apply to H-free graphs, confirming a bound on max-cut size dependent on the edges present.
This research advances existing conjectures in graph theory and adds to literature concerning eigenvalues and max-cut.

Abstract

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 λ₂ n^1/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 12. 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 m2 + n^1. 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 m2 + cH m^0. 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.

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

Key Points

Abstract

Cite This Study