Rank-sensitive vertex bounds for semidefinite lifts
Abstract
We study how the ranks of factors in a positive semidefinite slack factorization constrain its size. We bound the number of low-rank vertex factors in any fixed factorization, and use this to determine the asymptotic order of the minimum factorization size under any fixed bound on vertex-factor ranks: Θ(nlog n) for permutahedra Πn and Θ(log N) for regular N-gons. In the rank-one case this gives the order of the minimum dimension of a space of real functions on the vertices in which every facet slack is a sum of squares, with no symmetry or degree restriction. For unrestricted lifts, the bound gives xcPSD(Πn)≥ n+log3 n−O(1), and shows that a permutahedron factorization of linear size would need vertex factors of rank Ω(log n) at all but a vanishing fraction of vertices. We also prove that every polytope of real positive semidefinite rank at most four has at most twelve vertices, and construct explicit size-four lifts for every square-symmetric octagon, so eight is attained. The upper bound combines a count of the polygon corners reached by curves of rank-one factors with incidence constraints on factor ranks. Whether eight is the maximum remains open.
Related
- Lifts of Brauer characters and vertex pairs for odd primes
- One-Vertex Lifts of Looped Circle Graphs: Obstructions and Interlace Polynomials
- Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization
- Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing
- On Completely Positive and Semidefinite Programs for Moment Bounds on Maximum of Random Quadratics
BibTeX
@misc{bhardwaj2026ranksensitive,
title = {{Rank-sensitive vertex bounds for semidefinite lifts}},
author = {Avinash Bhardwaj},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04498},
eprint = {2610.04498},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04498},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Rank-sensitive vertex bounds for semidefinite lifts
AU - Avinash Bhardwaj
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.04498
UR - https://arxiv.org/abs/2610.04498
AB - We study how the ranks of factors in a positive semidefinite slack factorization constrain its size. We bound the number of low-rank vertex factors in any fixed factorization, and use this to determine the asymptotic order of the minimum factorization size under any fixed bound on vertex-factor ranks: Θ(nlog n) for permutahedra Π_n and Θ(log N) for regular N-gons. In the rank-one case this gives the order of the minimum dimension of a space of real functions on the vertices in which every facet slack is a sum of squares, with no symmetry or degree restriction. For unrestricted lifts, the bound gives xc_PSD(Π_n)≥ n+log_3 n−O(1), and shows that a permutahedron factorization of linear size would need vertex factors of rank Ω(log n) at all but a vanishing fraction of vertices. We also prove that every polytope of real positive semidefinite rank at most four has at most twelve vertices, and construct explicit size-four lifts for every square-symmetric octagon, so eight is attained. The upper bound combines a count of the polygon corners reached by curves of rank-one factors with incidence constraints on factor ranks. Whether eight is the maximum remains open.
ER -