Exponential semidefinite complexity of perfect matching

1 · The essentials

A perfect matching pairs up all the vertices of a graph, using each vertex exactly once. The manuscript studies these pairings when every pair of vertices is connected by an edge. It asks how compactly all possible pairings can be represented using a particular kind of mathematical description based on matrices. The main conclusion is that an exact description of this kind must have size that grows exponentially with the number of vertices. This rules out the polynomial-size descriptions asked about in the question attributed to Rothvoss in the repository summary. The result also applies to a related table of numbers after a fixed small positive amount is added to every entry. The main result has a Lean formalization, although the supplied text does not specify its detailed scope.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine trying to replace a huge catalog of possible seating pairs with a compact rulebook that captures exactly the same choices. The result says that, for the particular matrix-based rulebooks studied here, an exact replacement must still be exponentially large; it does not say this about every conceivable way of describing the catalog.

Why it matters

The result establishes a limitation on exact semidefinite descriptions of the perfect matching polytope. According to the repository summary, it answers Rothvoss’s polynomial-size lift question negatively. Its matrix lower bound allows arbitrary real positive semidefinite factors, rather than imposing an additional restriction on those factors.

2 · Going further

Let $n$ be even, and let $K_{n}$ be the graph with an edge between every pair of distinct vertices. The manuscript considers a matrix whose rows are indexed by odd-cardinality vertex sets $U$ and whose columns are indexed by perfect matchings $M$ . Writing $δ (U)$ for the edges with exactly one endpoint in $U$ , its entries are $∣ M \cap δ (U) ∣ - 1 + ρ$ . For every fixed $0 < ρ < 1$ , the stated result is that this matrix has real positive semidefinite rank $2^{Ω (n)}$ as even $n$ tends to infinity.

Positive semidefinite rank measures the smallest matrix dimension in a factorization of the entries as trace products of positive semidefinite matrices. The repository summary explicitly allows arbitrary real positive semidefinite factors. The abstract states that the exponential rank lower bound consequently forces every exact semidefinite lift of the perfect matching polytope to have exponential size. In this setting, a lift is a description of the polytope as a projection of a set described by positive semidefinite constraints.

The context supplied is Rothvoss’s question about a polynomial-size semidefinite lift, which the repository summary says is answered negatively. The abstract presents the route from a shifted-matrix rank lower bound to a lift-size lower bound, but does not describe the argument establishing that rank bound. Only the main manuscript is supplied, so no relationship to companion manuscripts can be described. The main result has a Lean formalization; the supplied material does not identify which additional claims or consequences it covers.

Useful notions

Graphs and perfect matchings
Odd vertex sets and edge cuts
Polytopes and projections
Positive semidefinite matrices
Polynomial versus exponential growth

What was known before / what is new

Before

The repository summary identifies a question attributed to Rothvoss asking for a polynomial-size semidefinite lift of the perfect matching polytope. The supplied text gives no further account of earlier bounds or methods.

New

The manuscript’s main result gives an exponential real positive semidefinite rank lower bound for the odd-cut matching matrix after every fixed shift $0 < ρ < 1$ . The abstract states the consequence that every exact semidefinite lift of the perfect matching polytope has exponential size. The repository summary describes this as a negative answer to Rothvoss’s question.

Limits and assumptions

The matrix result concerns perfect matchings of $K_{n}$ , with even $n$ tending to infinity, and a shift $ρ$ fixed strictly between zero and one. Its factors may be arbitrary real positive semidefinite matrices. The lift-size conclusion concerns exact descriptions; the supplied text does not state a result about approximate lifts, shifts depending on $n$ , or the endpoints of the shift interval. The main result has a Lean formalization, but its detailed coverage is not supplied, so verification of every stated consequence should not be assumed. No further open problems are specified in the supplied material.

Mini glossary

Perfect matching: A set of edges that pairs up all vertices, with each vertex belonging to exactly one chosen edge.
Edge cut: For a vertex set $U$ , the cut $δ (U)$ consists of the edges with one endpoint in $U$ and the other outside it.
Perfect matching polytope: The convex hull of the vectors recording which edges belong to each perfect matching.
Positive semidefinite matrix: A real symmetric matrix $A$ for which $x^{T} A x \geq 0$ for every real vector $x$ .
Positive semidefinite rank: The smallest dimension of positive semidefinite matrix factors whose pairwise trace products reproduce the entries of a given matrix.
Semidefinite lift: A representation of a polytope as the projection of a higher-dimensional set described by positive semidefinite constraints.

Keywords : Perfect matching · Positive semidefinite rank · Semidefinite lifts

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

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.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/126.md

Manuscripts in this family

★

Exponential PSD rank of positively shifted matching matrices

05/10/2026

To be verified

For every fixed $0 < ρ < 1$ , the matrix indexed by odd vertex sets U and perfect matchings M of K_n, with entries $∣ M \cap δ (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.

PDF GitHub folder