Exponential semidefinite complexity of perfect matching

The explanation

Six people must split into three pairs. There are 15 ways to do it. Each way is called a perfect matching. Now circle three of the six, say persons 1, 2 and 3. A group with an odd number of people is an odd set. Some pairs then cross the circle, with one partner inside and one outside. Of the 15 matchings, 9 have exactly one crossing pair and 6 have three. None has zero or two. An odd set always forces an odd number of crossings.

Now build a table with one row per odd set and one column per matching. Six people have 32 odd sets: 6 singles, 20 triples and 6 groups of five. So the table has 32 rows, 15 columns and 480 cells. Pick a fixed shift ρ (the Greek letter rho) between 0 and 1. In each cell, write the number of crossing pairs, minus 1, plus ρSource 1. With ρ = 1/2, 360 cells hold 0.5 and 120 cells hold 2.5Source 2. The paper studies this table for every even number n of people.

The table comes from geometry. Write each matching as a list of 0s and 1s, one entry per possible pair. These lists are the corners of a shape called the perfect matching polytope. In 1965 Jack Edmonds described this shape with simple inequalities. Many of them say that each odd set has at least one crossing pair. The table with ρ = 0 records each corner's slack (how far it sits from each such wall).

How compactly can the shape be described? One way is a lift: show the shape as the shadow of a simpler object in more dimensions. A semidefinite lift builds that object from positive semidefinite matrices. These are symmetric square grids of numbers whose matching quadratic expression is never negative. The lift's size is the side length of the grids. Gouveia, Parrilo and Thomas linked the smallest size to one number of the slack table. It is the table's positive semidefinite rank, or PSD rank. That is the smallest r for which each row and each column gets an r-by-r such matrix. Pairing a row's matrix with a column's matrix must give the cell's value exactly.

At ρ = 1 a cheap recipe existsSource 3. Use one diagonal slot per possible pair, which gives 15 slots for six people. A row's matrix marks the pairs that cross its odd set. A column's matrix marks the pairs in its matching. Pairing them counts crossing pairs, which is the cell's value when ρ = 1. This size grows only like n squared. The paper notes that ρ = 1 must therefore be left out of its resultSource 4.

The earlier work all used simpler kinds of recipe. In 1991 Mihalis Yannakakis built the factorization framework. He proved an exponential bound for symmetric linear descriptions. In 2017 Thomas Rothvoss proved the exponential bound for all linear descriptions. Semidefinite lifts can be far smaller than linear ones, so that bound does not carry overSource 5. Braun and Pokutta handled this shifted table in 2015, with plain nonnegative numbers in place of matrices. Braun and coauthors proved exponential bounds for symmetric semidefinite descriptions in 2017. Lee, Raghavendra and Steurer gave a general method for unrestricted semidefinite bounds in 2015. This paper follows their methodSource 6.

The single obstacle is that the matrices may be anything. No symmetry, sparsity or limited precision is assumedSource 7. The proof must average a row's matrix over many cuts, but averages and squares do not trade placesSource 8. The paper instead writes each average exactly as a sum of squares and controls those piecesSource 9. The contradiction comes from an impossible parity puzzle, built into groups of people inside the matchingSource 10.

The paper claims to prove that the shifted table has exponential PSD rankSource 11. There is one constant c above zero that works for every fixed ρ strictly between 0 and 1. For large even n, the rank is at least 2 to the power cnSource 11. As a consequence, the unshifted table also has exponential rank. So every exact semidefinite lift of the perfect matching polytope would have exponential sizeSource 12. Compare that with the 15 slots, or n squared growth, available at ρ = 1.

Three limits matter. The paper gives no number for c. It takes c = 1/(2k), where k is a large fixed group size that is never computedSource 13,Source 14. The size of n where the bound starts depends on ρSource 15. And exactness is essential. Kaniewski, Lee and de Wolf built tables of smaller than exponential PSD rank that match the unshifted table almost exactly. Their entries miss by at most 2 to the power minus the square root of n/2.

How sure is this? A computer proof checker called Lean has checked weaker versions, according to the Lean scope note. Pick any fixed power C. For large even n, a perfect-matching slack table has PSD rank above n to the power C. Every exact semidefinite lift likewise needs size above n to the power C. That is faster than any polynomial, but it is not the exponential bound for every shift. The exponential claim lies outside that check. No specialist review has been published.

What it doesn't show. This does not rule out small semidefinite descriptions that are only approximately correct.