Symmetric Extension Complexity of the Spanning Tree Polytope

In this note, we prove a tight lower bound on symmetric extended formulations for the spanning tree polytope of the complete graph. More precisely, let $P_{ST}(K_n)$ be the spanning tree polytope of $K_n$. We show that, for all $n\ge 13$, every symmetric extended formulation for $P_{ST}(K_n)$ has at least $\left(\genfrac{}{}{0px}{}{n}{3}\right)$ inequalities. Since the classical Martin formulation has a symmetric formulation of size $O(n^3)$, this gives $$\mathrm{xcs}(P_{ST}(K_n))=\mathrm{\Theta }(n^3)\mathrm{.}$$