Does the perfect matching polytope have a polynomial-size semidefinite lift?

A semidefinite lift of size $r$ writes a polytope as an affine image of $L\cap\mathbb S^r_+$ for an affine subspace $L$ ; by Gouveia-Parrilo-Thomas the least such $r$ equals the PSD rank of a slack matrix. Yannakakis ruled out small symmetric linear programs for the perfect matching polytope, Rothvoss (2014) proved its linear extension complexity is $2^{\Omega(n)}$ , and Braun et al. ruled out small symmetric SDPs, noting that it is natural to ask whether matching can be expressed compactly by semidefinite programming. Does the perfect matching polytope of $K_n$ admit an exact semidefinite lift of size polynomial in $n$ ?

Result: Disproved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Extended formulations; positive semidefinite rank, lower bounds
Posed by: G. Braun, J. Brown-Cohen, A. Huq, S. Pokutta, P. Raghavendra, A. Roy, B. Weitz, D. Zink, The matching problem has no small symmetric SDP, SODA 2016 / Math. Program. 165 (2017)
Year posed: 2015
Years open: 11y
Solved: 2026-10-05
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 35 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: there is $c>0$ such that for every fixed $0<\rho<1$ the odd-cut matrix with entries $|M\cap\delta(U)|-1+\rho$ has real PSD rank at least $2^{cn}$ for large even $n$ , with no symmetry or precision restriction on the factors. Corollary 1.2: every exact semidefinite lift of the perfect matching polytope has size $2^{\Omega(n)}$ . The method follows Lee-Raghavendra-Steurer with a Grigoriev-type parity functional and new averaging lemmas. The endpoint $\rho=1$ has a polynomial factorization, and approximate lifts are not excluded (Kaniewski-Lee-de Wolf give subexponential approximations).

What the AI did

The release README says all results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 and Corollary 1.2 were read against the question. The paper claims $\mathrm{rank}_{psd}A_n(\rho)\ge2^{cn}$ for every fixed $0<\rho<1$ and hence that every exact semidefinite lift of the perfect matching polytope has size $2^{\Omega(n)}$ . Proof not refereed. The challenges ComparatorChallenges/MatchingAffineLift.lean and MatchingPSD.lean are not in lean/formalization.yaml; they are found through lean/docs/126.md and their solution modules (OAI.Combinatorics.MatchingPSD.AffineLift and .Main) exist at the pinned commit. Statements read here: for every $C>0$ and large even $n$ , every affine section of a PSD cone projecting onto the matching polytope has size $>n^C$ , and the PSD rank of the unshifted slack matrix exceeds $n^C$ . This states the headline (no polynomial-size lift); the exponential bound and the shifted matrices are not formalized. Not rebuilt here.

Does the perfect matching polytope have a polynomial-size semidefinite lift?

What was actually shown

What the AI did

Verification

Sources

Discussion