Spectral and Probabilistic Guarantees for Greedy Max-Cut

We study the greedy vertex-flip algorithm for the Max-Cut problem and establish structural and probabilistic guarantees on its behavior. We show that spectral properties of the graph constrain the distribution of local gains, and we derive lower bounds on expected improvement under a gain-weighted randomized variant of greedy descent. Using these bounds, we prove high-probability convergence guarantees expressed in terms of gain distribution and graph structure. In addition to convergence guarantees, we derive a spectral lower bound on the cut value produced by greedy Max-Cut, providing an approximation-style guarantee linked to graph structure. Our results provide a unified framework connecting spectral graph theory, local search dynamics, and stochastic convergence.