A Structural Gain Dichotomy for Greedy Max-Cut and Its Convergence

This paper develops a structural framework for analyzing the convergence of the randomized greedy vertex-flip algorithm for the Max-Cut problem and forms part of an ongoing research program on the structural and spectral analysis of greedy algorithms in combinatorial optimization. A central obstacle in prior analyses is the reliance on lower bounds for total positive gain, which are not known to hold uniformly across all configurations. This work addresses that issue by introducing a structural gain dichotomy: any configuration with nontrivial imbalance must either exhibit sufficiently large total positive gain to drive meaningful improvement, or already lie in a low-energy regime corresponding to a high-quality cut. This principle replaces externally imposed gain assumptions with an intrinsic structural condition. Using this framework, the paper derives bounds on expected improvement and establishes convergence guarantees via a monotone energy argument, showing that the process reaches an ε-stationary state within O(nd/ε) expected steps. As part of a broader research direction, this work contributes toward an unconditional structural theory of greedy local search, in which algorithmic progress is governed by global constraints rather than purely local behavior.