{"id":"arxiv/2606.17017","url":"https://arxiv.org/abs/2606.17017","tags":["math.CO","math.OC"],"score":0,"title":"(Approximate) Symmetric Extension Complexity of the Spanning Tree Polytope","domain":"math.CO","source":"arxiv","authors":["Sebastian Pokutta"],"reviews":0,"subject":"math.CO","summary":"We prove a tight lower bound on symmetric LP 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). \\] We also study outer relaxations of the spanning tree polytope of $K_n$ for maximization with nonnegative edge weights. We show that for every…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}