OctoInformBeta

Exponential semidefinite complexity of perfect matching

For even n≥4n\ge4, let ℳn\mathcal M_n denote the perfect matchings of the complete graph KnK_n on nn vertices. For a vertex subset UU, let δ(U)\delta(U) denote its edge cut. For 0≤ρ≤10\le\rho\le1, define the matrix An(ρ)A_n(\rho), indexed by odd vertex subsets UU and perfect matchings M∈ℳnM\in\mathcal M_n, by An(ρ)U,M=|M∩δ(U)|−1+ρA_n(\rho)_{U,M}=|M\cap\delta(U)|-1+\rho. The real PSD rank rank⁡psdA\operatorname{rank}_{\mathrm{psd}}A of a nonnegative matrix AA is the least positive integer rr admitting real symmetric positive semidefinite factors of order rr whose trace pairings equal the entries of AA. Let Tn(0)T_n(0) be obtained from An(0)A_n(0) by adjoining the edge rows Tn(0)e,M=𝟏{e∈M}T_n(0)_{e,M}=\mathbf1_{\{e\in M\}}. The perfect matching polytope PnP_n is the convex hull of the incidence vectors of the matchings in ℳn\mathcal M_n. An exact semidefinite lift of size rr represents PnP_n as an affine image of an affine slice of the cone of real symmetric positive semidefinite matrices of order rr. The question is whether exact PSD factorizations of these matching matrices can have size polynomial in nn.

Edmonds described PnP_n 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 An(ρ)/2A_n(\rho)/2 for each fixed 0<ρ<10<\rho<1. 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 c>0c>0 such that, for every fixed 0<ρ<10<\rho<1, rank⁡psdAn(ρ)≥2cn\operatorname{rank}_{\mathrm{psd}}A_n(\rho)\ge2^{cn} for all sufficiently large even nn. The preprint derives an exponential lower bound for exact semidefinite lifts of PnP_n that is not contained in the Lean library.

For every real C>0C>0, the Lean library proves rank⁡psdTn(0)>nC\operatorname{rank}_{\mathrm{psd}}T_n(0)>n^C for all sufficiently large even nn. For every real C>0C>0, the Lean library proves that every exact affine semidefinite lift of PnP_n has size greater than nCn^C for all sufficiently large even nn. 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.