Extended formulations for sparsity matroids.

We show the existence of a polynomial-size extended formulation for the base polytope of a $$(k,\ell )$$ -sparsity matroid. For an undirected graph $$G=(V,E)$$ , the size of the formulation is $$O(|V|\cdot |E|)$$ when $$k \ge \ell $$ and $$O(|V|^2 |E|)$$ when $$k \le \ell $$ . To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol. [ABSTRACT FROM AUTHOR]