Quantitative Bounds on Local Improvement in Greedy Max-Cut via Spectral Structure

We study the greedy vertex-flip algorithm for the Max-Cut problem and derive explicit lower bounds on the maximum local improvement in terms of global graph structure. While it is known that greedy local search converges to a 1-flip local optimum, standard analyses do not provide direct quantitative bounds on the best available move at a given configuration. We show that for any cut vector x ∈ {−1, 1}^n, the maximum local gain admits a lower bound in terms of the quadratic form x^T A x. This establishes a deterministic global-to-local relationship linking adjacency structure to local descent. We further show that this bound yields polynomial-time convergence in unweighted graphs, with explicit control on per-step improvement. In regular graphs, the result admits a direct spectral interpretation. All arguments are self-contained and operate entirely within the discrete setting. The results provide a concrete characterization of how global structure constrains local search in combinatorial optimization.