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\ge13$, every symmetric extended formulation for $P_{ST}(K_n)$ has at least $\binom n3$ 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). ]

Source: arXiv:2606.17017v1 - http://arxiv.org/abs/2606.17017v1 PDF: https://arxiv.org/pdf/2606.17017v1 Original Link: http://arxiv.org/abs/2606.17017v1