Exponential semidefinite complexity of perfect matching

What OpenAI claims

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 < ρ < 1, allowing arbitrary real positive semidefinite factors. (Lean)

Paper

1. Exponential PSD rank of positively shifted matching matrices

   5 October 2026 · Preprint, not peer reviewed · PDF

   For every fixed 0 < ρ < 1, the matrix indexed by odd vertex sets U and perfect matchings M of Kn, with entries |M∩δ(U)|-1+ρ, has real positive semidefinite rank 2^Ω(n) as even n tends to infinity. Here δ(U) is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.