Optimal solution ranks in the Max-Cut semidefinite relaxation
math.OC, math.CO
Submitted: 2026-10-25
Updated: 2026-10-25
License: http://creativecommons.org/licenses/by/4.0/
The gist: For every n and r with 1 at most r and 2 at most n, we construct a connected unweighted graph on n vertices whose Max-Cut semidefinite relaxation has a unique optimal solution of rank r.
Abstract
For every n and r with 1 at most r and 2 at most n, we construct a connected unweighted graph on n vertices whose Max-Cut semidefinite relaxation has a unique optimal solution of rank r. The main examples are the Kneser graphs K(m,2), whose unique optima have rank m-1. A six-vertex wheel supplies rank three, and attaching pendant vertices preserves both rank and uniqueness. For dense random graphs, we also prove a polynomial lower bound on the optimal rank.
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise