Lexicographically minimal maximal sparse paving matroids have exponential extension complexity

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.

Sources & referencesView supporting material

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.