Skip to content
DraconiticResearch
Search Sources API
182,460 studies31 sourcesUpdated 16 min ago
PreprintCC BY 4.0arXiv

Optimal solution ranks in the Max-Cut semidefinite relaxation

  • Avinash Bhardwaj
  • Vishnu Narayanan
Open at sourcePDFDOICite

Abstract

For every n and r with 1≤ r and binomr+12≤ 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

  1. Maximum Intersecting Families of Submultisets: A Complete Solution over All Ranks and Exact Results at Fixed Rank
    Sunitha K G, Girish K P
    HALPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsHAL
  2. Optimal Actuator Design across Ranks and Control Horizons
    Emmanuel Trélat, Enrique Zuazua
    HALPreprintPublisher termsFull textOptimisation & controlHALarXiv
  3. Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
    Avinash Bhardwaj, Chen Chen, Vishnu Narayanan
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing
    Mingxuan Sun, Zhiqiang Xu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsNumerical analysis & scientific computingarXiv
  5. Optimal relaxation for Witten Lindbladians
    Simon Becker, Maciej Zworski
    arXivPreprintCC0Full textAnalysis & PDEsMathematical physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bhardwaj2026optimal,
  title = {{Optimal solution ranks in the Max-Cut semidefinite relaxation}},
  author = {Avinash Bhardwaj and Vishnu Narayanan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.34324},
  eprint = {2610.34324},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.34324},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Optimal solution ranks in the Max-Cut semidefinite relaxation
AU  - Avinash Bhardwaj
AU  - Vishnu Narayanan
PY  - 2026
DA  - 2026/10/25
PB  - arXiv
DO  - 10.48550/arxiv.2610.34324
UR  - https://arxiv.org/abs/2610.34324
AB  - For every n and r with 1≤ r and binomr+12≤ 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.
ER  -