Lower Bounds for Approximating the Matching Polytope

We prove that any linear program that approximates the matching polytope on n-vertex graphs up to a factor of (1+\eps) for any 2/n <=  \eps <= 1 must have at least \binom{n}{\alpha/\eps} inequalities where 0<\alpha<1 is an absolute constant. This is tight as exhibited by the (1+\eps) approximating linear program obtained by dropping the odd set constraints of size larger than O(1/\eps) from the description of the matching polytope. Previously, a tight lower bound of 2^{\Omega(n)} was only known for \eps = O(1/n) (Rothvoss, Journal of the ACM ‘17; Braun and Pokutta, IEEE Trans. Information Theory '15) whereas for 2/n <= \eps <= 1, the best lower bound was 2^{1/\eps} (Rothvoss, Journal of the ACM ‘17). The key new ingredient in our proof is a close connection to the non-negative rank of a lopsided version of the unique disjointness matrix.