Family 126Theoretical computer scienceNo LeanNot yet digested

Exponential semidefinite complexity of perfect matching

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.

Manuscripts in this family · 1

Exponential PSD rank of positively shifted matching matrices

Oct 5, 2026·shifted-matching-psd.pdf

For every fixed

0\lt \rho\lt 1

, the matrix indexed by odd vertex sets U and perfect matchings M of K

_{n}

, 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.

Full abstract

PDF on GitHub LaTeX source