Metraipolis › archive › dc_2b410eb1df41
The Geometry of Optimal Max-Cut SDP Solutions — arXiv:2609.36827
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.36827
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:02:01.510Z
- SHA-256 of the archived text
ba5bf919c5dc8ff9781a05349bdb0c070561d0e952c0ec2394249098506f3122- Stable URL of this page
https://metraipolis.com/documento/dc_2b410eb1df41
How to cite
The Geometry of Optimal Max-Cut SDP Solutions — arXiv:2609.36827 — arXiv (en), https://arxiv.org/abs/2609.36827 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2b410eb1df41 (Metraipolis archive dc_2b410eb1df41, sha256 ba5bf919c5dc8ff9781a05349bdb0c070561d0e952c0ec2394249098506f3122)
BibTeX
@misc{dc2b410eb1df41,
title = {The Geometry of Optimal Max-Cut SDP Solutions — arXiv:2609.36827},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.36827},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2b410eb1df41; sha256 ba5bf919c5dc8ff9781a05349bdb0c070561d0e952c0ec2394249098506f3122},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36827. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
When the semidefinite relaxation of Max-Cut is exact, its optimal cut sign vectors lie in the kernel of the optimal dual slack. We study when they span this kernel and which matrices can occur as certificates with this property. Our main result realizes every doubly nonnegative matrix with positive diagonal and rational kernel, after sufficiently large even replication, as such a certificate. Replication preserves rank, complete positivity, and cp-rank when finite. In particular, connected exact instances with non-completely-positive sign-spanned slacks exist at every rank at least three, including an explicit fourteen-vertex example. We also characterize the arithmetic obstruction: some positive column replication has a sign-spanned kernel if and only if the original kernel is rational. For arbitrary real kernels, we determine the eventual spanning deficit. A multiplicity formula separates the contributions of repeated-column blocks and their feasible sums. Further results distinguish cut spans from optimal-face geometry, characterize orthogonal extremality through uniform complete graphs and Hadamard matrices, and give determinant bounds supporting exact finite classifications. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.OC). Categorie arXiv: Optimization and Control (math.OC). Pagina del lavoro: https://arxiv.org/abs/2609.36827 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T17:35:03.540Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).