Spectral Descent and Polynomial-Time Convergence of Greedy Max-Cut under Structural Conditions

We study the behavior of greedy local search for the Max-Cut problem through a spectral lens. While it is well known that simple vertex-flip heuristics converge to a 1-flip local optimum, little quantitative structure is typically provided on the magnitude of local improvements or the role of graph structure in governing convergence behavior. In this work, we establish a direct relationship between global spectral properties of the graph and the existence of locally improving moves. Specifically, we derive a spectral lower bound on the maximum gain obtainable by a single vertex flip, expressed in terms of the adjacency quadratic form. This yields a global-to-local bridge: whenever the current cut is spectrally suboptimal, there exists a provably improving move. We further show that, in d-regular graphs, the spectral gap influences the qualitative rate of convergence. Under structural conditions, the greedy flip algorithm exhibits accelerated descent behavior, with convergence to a 1-flip local optimum in polynomial time. These results provide a clean and explicit framework connecting spectral structure, local improvement, and convergence behavior, offering a structural perspective on descent dynamics in combinatorial optimization without relying on relaxations or randomized methods.