Lexicographically minimal maximal sparse paving matroids have exponential extension complexity

About 3 years old · traced to

For each positive integer nn, let Sn\mathsf{S}_n be the sparse paving matroid on [n][n] of rank ⌊n/2⌋\lfloor n/2\rfloor with the maximal possible number of circuit-hyperplanes and lexicographically minimal set of bases. The extension-complexity conjecture. For every positive integer nn, its base polytope satisfies

xc⁡(P(Sn))∈Ω(2n/2n5/4log⁡(2n)).\operatorname{xc}(\mathscr{P}(\mathsf{S}_n)) \in \Omega\left(\frac{2^{n/2}}{n^{5/4}\sqrt{\log(2n)}}\right).

Rothvoss proved the existence of matroids with this asymptotic lower bound, but his argument is non-constructive; an explicit exponential family remains open. The conjecture proposes that this particular explicitly selected family has the desired extension complexity, with the construction of Sn\mathsf{S}_n itself also noted as an open problem.

References

Primary source

Luis Ferroni and Benjamin Schröter, “Face enumeration for split matroid polytopes”, arXiv:2310.05487 (2025).

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.