Rank-sensitive vertex bounds for semidefinite lifts

Source 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: $Θ(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 lifts, the bound gives $\mathrm{xc}_{\mathrm{PSD}}(Π_n)\ge 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.