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

This work studies the convergence behavior of the randomized greedy vertex-flip algorithm for the Max-Cut problem through a structural and spectral framework. A central obstacle in analyzing greedy Max-Cut dynamics is that convergence guarantees typically rely on lower bounds on total positive gain, which are not known to hold uniformly across all configurations. This work addresses that gap by identifying structural constraints that govern the distribution of local gains. The main contribution is the establishment of a gain dichotomy: for any configuration with nontrivial imbalance, either the total positive gain is sufficiently large to drive rapid progress, or the configuration is already close to a low-energy regime. This principle shows that low-gain configurations are necessarily structured and cannot occur far from near-optimal states. Using this dichotomy, the paper derives bounds on expected improvement and proves convergence guarantees that do not depend on externally imposed gain assumptions. This yields a two-phase convergence mechanism consisting of an initial drift phase driven by imbalance reduction, followed by a refinement phase near high-quality cuts. This work provides a structural explanation for the absence of stagnation in greedy Max-Cut dynamics and represents a step toward an unconditional theory of convergence for greedy local search in combinatorial optimization. This paper is part of an ongoing research program developing a structural theory of greedy Max-Cut dynamics.