The Setting
The representation sizes for the perfect matching polytope considered here are the real positive semidefinite (PSD) rank of its unshifted slack matrix and the order of an exact affine PSD lift.
Let , let be the complete graph on , and let be its edge set, the set of unordered pairs of distinct vertices in .✦ A perfect matching on is a subset of in which every vertex belongs to exactly one edge. Write for the set of perfect matchings on .
An odd cut is a subset of of odd cardinality; let be the set of these subsets.✦ An edge crosses when exactly one of its endpoints belongs to .✦ The cut and the crossing count are given by (1). (1)
The incidence vector of a perfect matching records edge membership.✦ The perfect matching polytope is the convex hull of the incidence vectors of the perfect matchings on , as in (2).✦ (2)
The row set distinguishes edge rows from odd-cut rows.✦ The unshifted slack matrix has columns indexed by and entries (3). Write for the submatrix of consisting of the odd-cut rows. (3)✦
For a nonnegative integer , let denote the cone of real symmetric PSD matrices of order . A real PSD trace factorization of of order is a pair of families , indexed by and , satisfying (4). (4)✦ The real PSD rank of is the least positive factor order in (5). (5)✦
An exact affine PSD lift of of order consists of an affine subspace and an affine map satisfying (6).✦ The size of an exact affine PSD lift of of order is . (6)
The Claim
Theorem 1. Fix a real . With an integer threshold chosen sufficiently large, every even satisfies (7). (7)✦ Fix a nonnegative integer . With an integer threshold chosen sufficiently large, every even satisfies (8). (8)✦ Fix a real . With an integer threshold chosen sufficiently large and even , every exact affine PSD lift of of order satisfies (9). (9)✦
In the paper, the result reads: there are and an integer such that, for every even , both and have real PSD rank at least , and every exact semidefinite lift of has size at least .
What Is Checked
The rank bounds (7) and (8) are stated over the full edge and odd-cut slack matrix with real PSD factors. The lift bound (9) concerns exact affine images of slices of real PSD cones, with exactness given by (6).
Theorem 2. Let be even, and suppose that has an exact affine PSD lift of order . There are families , indexed by and , with the matrix identity (10). (10)✦