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

About 10 years old · traced to

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.

References

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.