Lower Bounds for Approximating the Matching Polytope

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\epsilon )$ for any $\frac{2}{n}\le \epsilon \le 1$ must have at least $\left(\genfrac{}{}{0px}{}{n}{\alpha \mathrm{/}\epsilon }\right)$ defining inequalities where $0<\alpha <1$ is an absolute constant. This is tight as exhibited by the $(1+\epsilon )$ approximating linear program obtained by dropping the odd set constraints of size larger than $(1+\epsilon )\mathrm{/}\epsilon$ from the description of the matching polytope. Previously, a tight lower bound of $2^{\mathrm{\Omega }(n)}$ was only known for $\epsilon =O\left(\frac{1}{n}\right)$ [Rothvoss, STOC '14; Braun and Pokutta, IEEE Trans. Information Theory '15] whereas for $\frac2n \le \varepsilon \le 1$,thebestlowerboundwas$2^{\Omega\left({1}/{\varepsilon}\right)}$ [Rothvoss, STOC '14]. 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.