Proves that every exact semidefinite lift of the perfect matching polytope has exponential size, answering Rothvoss's polynomial-size lift question negatively. The bound holds even for the positive semidefinite rank of its odd-cut slack matrix after any fixed shift 0\lt \rho\lt 1, allowing arbitrary real positive semidefinite factors. (Lean)
Manuscript
Exponential PSD rank of positively shifted matching matrices
October 5, 2026 · source · cite as \cite{OAI:Exponential-PSD-rank-of-positively-shifted-matching-matrices-October-5-2026}
For every fixed 0\lt \rho\lt 1, the matrix indexed by odd vertex sets U and perfect matchings M of Kn, with entries |M\cap\delta(U)|-1+\rho, has real positive semidefinite rank 2^{\Omega(n)} as even n tends to infinity. Here \delta(U) is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.
Result 126 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md