For even , let denote the perfect matchings of the complete graph on vertices. For a vertex subset , let denote its edge cut. For , define the matrix , indexed by odd vertex subsets and perfect matchings , by . The real PSD rank of a nonnegative matrix is the least positive integer admitting real symmetric positive semidefinite factors of order whose trace pairings equal the entries of . Let be obtained from by adjoining the edge rows . The perfect matching polytope is the convex hull of the incidence vectors of the matchings in . An exact semidefinite lift of size represents as an affine image of an affine slice of the cone of real symmetric positive semidefinite matrices of order . The question is whether exact PSD factorizations of these matching matrices can have size polynomial in .
Edmonds described by nonnegativity and odd-cut inequalities within the affine space of degree equations. Rothvoß proved an exponential lower bound for unrestricted linear extension complexity of the matching polytope. Braun and Pokutta proved exponential nonnegative rank for the matrix for each fixed . The cone-factorization theorem of Gouveia, Parrilo and Thomas identifies the PSD rank of a slack matrix with the minimum size of a semidefinite lift.
The preprint proves that there is a constant such that, for every fixed , for all sufficiently large even . The preprint derives an exponential lower bound for exact semidefinite lifts of that is not contained in the Lean library.
For every real , the Lean library proves for all sufficiently large even . For every real , the Lean library proves that every exact affine semidefinite lift of has size greater than for all sufficiently large even . Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its Lean declaration. Where the preprint gives a different statement, that statement appears beside the Lean library’s statement. The preprint is a guide only, supplying the order and the names of the results.
MatchingPSD is a Lean library: 10 items, in three groups. Each has a page written by OctoInform, listed below.
No item matches.