Spectral Structure Forces Two-Phase Convergence in Greedy Max-Cut

This work studies the convergence behavior of the randomized greedy vertex-flip algorithm for the Max-Cut problem through a structural and spectral framework. We develop a unified perspective linking gain distribution, spectral constraints, and energy dynamics. The analysis shows that local improvements are globally constrained by spectral structure, which limits the distribution of positive gain and enforces measurable progress under natural conditions. The main result establishes a two-phase convergence mechanism. In the nontrivial regime, imbalance decays exponentially under a drift condition governed by spectral properties. In the near-trivial regime, convergence is controlled by a global energy descent bound, yielding an explicit time to ε-stationarity. A key feature of the analysis is the introduction of imbalance as a central parameter governing algorithmic progress, together with structural bounds connecting gain concentration and expected improvement. This version (V5) presents a complete structural framework for greedy Max-Cut dynamics. Subsequent versions will aim to weaken or eliminate the gain condition and further refine the convergence theory.