Linear extension complexity for minor-closed families
Conjecture 2 · arXiv:1604.07976
Status partial high confidence
The conjecture that $\mathrm{xc}(P_{\mathrm{sp.trees}}(G)) = O(|V|)$ for every proper minor-closed family $\mathcal{C}$ and connected $G \in \mathcal{C}$ remains open. The main post-2017 progress is due to Aprile, Fiorini, Huynh, Joret, and Wood (2021), who proved an $O(n^{3/2})$ upper bound for any proper minor-closed class (and more generally $O(n^{1+\beta})$ for classes with $O(n^\beta)$-size balanced separators), improving the previously known $O(n^2)$ bounds. The linear $O(n)$ bound has been established for planar graphs and for graphs of bounded treewidth, but the full conjecture for all proper minor-closed families is unresolved.
Cited literature (1)
-
partial Smaller Extended Formulations for Spanning Tree Polytopes in Minor-Closed Classes and Beyond (2021)
Proves $\mathrm{xc}(P_{\mathrm{sp.trees}}(G)) = O(n^{3/2})$ for connected $n$-vertex graphs in any proper minor-closed class, improving the $O(n^2)$ bound, but the conjectured $O(n)$ bound remains open.
Reviewer notes. The conjecture is open for general proper minor-closed families. The best known upper bound as of 2021 is O(n^{3/2}) by Aprile et al. (arXiv:2106.11945, EJC 2021). No 2022–2026 paper resolving the full conjecture was found in the search.
Context
Following Conjecture 1, the authors suggest the linear bound may hold even more generally for all proper minor-closed families. They note the conjecture is known to hold when graphs in $\mathcal{C}$ have bounded treewidth, and they prove it for $k$-apex graphs (Theorem 4) as additional supporting evidence.
Source paper
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs
Samuel Fiorini, Tony Huynh, Gwenaël Joret, Kanstantsin Pashkovich · 2017-01-09
https://arxiv.org/abs/1604.07976
PDF source