{"id":"arxiv/2610.04498","url":"https://arxiv.org/abs/2610.04498","tags":["math.OC","math.CO"],"score":0,"title":"Rank-sensitive vertex bounds for semidefinite lifts","domain":"math.OC","source":"arxiv","authors":["Avinash Bhardwaj"],"reviews":0,"subject":"math.OC","summary":"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: $Θ(n\\log 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-03","reactions":{}}