Symmetric Extension Complexity of the Spanning Tree Polytope

Sebastian Pokutta

paper

Symmetric Extension Complexity of the Spanning Tree Polytope

arXiv:2606.17017

Abstract

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_{S T} (K_{n})$ be the spanning tree polytope of $K_{n}$ . We show that, for all $n \geq 13$ , every symmetric extended formulation for $P_{S T} (K_{n})$ has at least $(3 n)$ inequalities. Since the classical Martin formulation has a symmetric formulation of size $O (n^{3})$ , this gives \[ \operatorname{xcs}(P_{ST}(K_n))=Θ(n^3). \]