Lexicographically minimal maximal sparse paving matroids have exponential extension complexity
Lexicographically minimal maximal sparse paving matroids have exponential extension complexity
For each positive integer , let be the sparse paving matroid on of rank with the maximal possible number of circuit-hyperplanes and lexicographically minimal set of bases. The extension-complexity conjecture. For every positive integer , its base polytope satisfies
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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.