Linear extension complexity conjecture for spanning tree polytopes of proper minor-closed graph families

Let C\mathcal{C} be a proper minor-closed family of graphs, and let G=(V,E)G=(V,E) be a connected graph in C\mathcal{C}. Let Psp.trees(G)\operatorname{P_{\mathrm{sp.trees}}}(G) denote the convex hull of the characteristic vectors of the spanning trees of GG. The minor-closed spanning tree polytope conjecture.

xc(Psp.trees(G))=O(V).\operatorname{xc}(\operatorname{P_{\mathrm{sp.trees}}}(G))=O(|V|).

This would extend the proposed linear bound from fixed-surface graph families to all proper minor-closed families. The source presents it as a further possible generalization, and it remains open.

Sources & referencesView supporting material

Primary source

Samuel Fiorini, Tony Huynh, Gwenaël Joret and Kanstantsin Pashkovich, “Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs”, arXiv:1604.07976 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.