Optimal solution ranks in the Max-Cut semidefinite relaxation

arXiv:2610.34324 · math.OC, math.CO · Submitted 2026-10-25 · Read on arXiv

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