{"id":"arxiv/2610.34324","url":"https://arxiv.org/abs/2610.34324","tags":["math.OC","math.CO"],"score":0,"title":"Optimal solution ranks in the Max-Cut semidefinite relaxation","domain":"math.OC","source":"arxiv","authors":["Avinash Bhardwaj","Vishnu Narayanan"],"reviews":0,"subject":"math.OC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-25","reactions":{}}