On the combinatorial lower bound for the extension complexity of the Spanning Tree polytope

This paper concerns the extension complexity of the Minimum Spanning Tree problem on a complete graph with  $n$ nodes. The best known lower bound is the trivial bound, $\Omega \left(n^2\right)$, the best known upper bound is the extended formulation size $O\left(n^3\right)$ (Wong 1980, Martin 1991). We give a nondeterministic communication protocol with cost ${log}_2(n^{2}logn)+O\left(1\right)$ for the support of the spanning tree slack matrix.