Optimal solution ranks in the Max-Cut semidefinite relaxation
For every $n$ and $r$ with $1\le r$ and $\binom{r+1}{2}\le 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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.34324
curl -X POST /api/v1/records/arxiv/2610.34324/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.34324/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'