Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 126: exponential semidefinite complexity of perfect matching

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This source-pinned article reports a publisher claim without independently validating the proof.

The question in plain language

A perfect matching pairs all vertices of a graph using edges that share no endpoints. The perfect matching polytope collects all incidence vectors of such matchings and everything obtainable as their convex combinations. Describing this polytope through a smaller higher-dimensional convex system could make optimization more efficient.

A semidefinite lift represents a convex set as a linear projection of a slice of a positive semidefinite matrix cone. Family 126 claims that no small exact semidefinite lift of the perfect matching polytope exists.

A small example

For four vertices, each perfect matching pairs vertices in two disjoint pairs. Its incidence vector has a 1 for each selected edge and a 0 for every unselected edge. Convex mixtures of these vectors form a polytope.

A linear or semidefinite lift may introduce auxiliary variables so the projected description is simpler than the original facet description. The size of a semidefinite lift is usually measured by the dimension of its positive semidefinite matrix, not simply by the number of inequalities in the original coordinates. An exact lift must represent the polytope itself, rather than only an approximation.

What is known

The protected Family 126 catalogue lists one manuscript, Exponential PSD rank of positively shifted matching matrices.

The pinned publisher overview claims that every exact semidefinite lift of the perfect matching polytope has exponential size, answering a polynomial-size-lift question attributed to Rothvoss negatively.

The overview also asserts an exponential lower bound for the positive semidefinite rank of the odd-cut slack matrix even after any fixed positive shift satisfying \(0<\rho<1\), while allowing arbitrary real positive semidefinite factors. This strengthened shifted-matrix claim must be distinguished from the unshifted perfect-matching lift conclusion.

A positive semidefinite factorization represents entries of a nonnegative matrix by inner products of positive semidefinite matrices. The least feasible matrix dimension is its PSD rank. Relating this rank to exact semidefinite extension complexity requires a precise slack-matrix/factorization theorem and normalization.

The statement concerns exact semidefinite representations. It is not, without additional assumptions, a lower bound for every approximate semidefinite relaxation or an assertion that polynomial-time perfect-matching optimization is impossible.

GCL verification state

Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. The protected source catalogue identifies the manuscript and the pinned publisher overview states the exponential exact-lift and shifted PSD-rank claims.

This documentary pass has not verified the PSD-rank lower-bound argument, odd-cut slack matrix indexing, shift convention, allowable real factors, or the derivation from factorization size to extension complexity. No Family 126-specific accepted critical proof audit, Comparator result, formal elaboration, or MATHCERT certificate is asserted.

What remains

Read the pinned PDF and extract the exact theorem and the graph-size parameter in its exponential bound. Check the vertex/edge indexing of the odd-cut slack matrix and the exact operation meant by “positive shift.” Determine whether constants depend on fixed \(\rho\) and how the quantifiers range over all real PSD factorizations.

Audit the lower-bound proof, including its communication-complexity or information-theoretic ingredients if used, and verify the slack-matrix factorization correspondence for the exact matching polytope. Separate exact-lift consequences from any approximation claims, and reconcile the result with known polynomial-time combinatorial perfect-matching algorithms.

Complete mathematical Markdown/MkDocs regression, source-critical review, and protected merge/readback. Editorial acceptance alone is not proof certification.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. Both exponential-size claims remain publisher-reported pending independent mathematical verification.


Indexed primary manuscript paths: