MathDB

The paving matroid conjecture

About 10 years old · traced to

A rank-rr matroid is paving if all its circuits have cardinality at least rr. For each positive integer nn, consider matroids on an nn-element ground set. The paving matroid conjecture. Asymptotically almost all matroids on nn elements are paving. This conjecture is central in asymptotic matroid theory and is attributed to Mayhew, Newman, Welsh, and Whittle. If true, it would yield a (1+o(1))(1+o(1))-competitive matroid secretary algorithm for almost all matroids.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Paving matroid conjecture

    Let M(n)\mathbb{M}(n) be the set of matroids on an nn-element ground set. A matroid is paving when every circuit has size at least its rank.

    Paving conjecture. Asymptotically almost all matroids are paving.

    By duality, this would also imply that asymptotically almost all matroids are sparse paving; in the paper it is noted that the conjecture would immediately imply the asymmetry conjecture. It remains open in the supplied text.

    source: Rudi Pendavingh and Jorn van der Pol, “Asymptotics of Symmetry in Matroids”, arXiv:1609.04975 (2016).

References

Primary source

Tony Huynh and Peter Nelson, “The matroid secretary problem for minor-closed classes and random matroids”, arXiv:1603.06822 (2019).

enumerative-combinatoricsmatroid-secretarymatroid-theory
Posted · edited

Progress summary

Refreshed
Open

No public source reports a proof or counterexample; the conjecture remains open.

The conjecture says that, as the ground set grows, almost every matroid is paving. It is attributed to Mayhew, Newman, Welsh, and Whittle, and remains explicitly stated as open in the retrieved literature.

Known results

  • The number of sparse paving matroids has the same logarithmic asymptotics as the number of all matroids: log⁡s(n)∼log⁡m(n)\log s(n)\sim\log m(n); the stronger asymptotic equivalence is conjectural. [Mayhew–Newman–Welsh–Whittle, 2016]
  • Earlier work proved lim⁡n→∞log⁡sn/log⁡mn=1\lim_{n\to\infty}\log s_n/\log m_n=1 and concentration of the rank near n/2n/2, but not that almost all matroids are paving. [2015]
  • If the conjecture holds, almost all matroids admit a (1+o(1))(1+o(1))-competitive matroid secretary algorithm.

Current status (as of September 2026): The paving matroid conjecture remains open; related logarithmic counting results are known, but no proof, counterexample, or claimed resolution was found.

Sources

Solutions 0

No solutions have been posted yet.