Semidefinite lifts of the perfect matching polytope

The shifted matching matrices, with entries |M ∩ δ(U)| − 1 + ρ for odd sets U and perfect matchings M of the complete graph K_n, have positive semidefinite rank 2^{Ω(n)} for every fixed 0 < ρ < 1; consequently every exact semidefinite lift of the perfect matching polytope has exponential size. Averaging row factors over restrictions of cuts to cells, an orthogonal splitting inequality and a Fourier smoothing theorem turn a small factorization into an approximation of a parity function on an expanding graph by squares of low degree, which a functional of Grigoriev type rules out. The course is an exposition of OpenAI's proof (2026), with a further smoothing theorem for averages over perfect matchings.

Seven lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. PSD factorizations and semidefinite lifts
2. Averaging within a cell
3. Splitting positive semidefinite matrices
4. Fourier smoothing of matrix squares
5. An expanding parity system
6. The lower bound for perfect matching
7. Uniform smoothing of matching averages

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• The symmetric groups II: branching, Jucys–Murphy elements and Young's seminormal form · Open Mathematics Courses (Representations of finite groups)
• The symmetric groups I: Young tableaux and Young symmetrizers · Open Mathematics Courses (Representations of finite groups)
• The spectral theorem for real symmetric matrices (linear algebra); for the seventh lesson, Young diagrams, the branching rule and the dimension formula for the symmetric group (course Representations of finite groups, lessons on the symmetric groups).