The number of partial Steiner systems and d-partitions

The notion of linear dependence is pervasive throughout mathematics. In 1935, Hassler Whitney, and independently Takeo Nakasawa, introduced the notion of a matroid to abstractly encapsulate this notion. A matroid on a finite set \(E\) is a nonempty hereditary collection of subsets of \(E\) called independent sets such that every subset \(Z\) of \(E\) has all of its maximal independent sets having the same cardinality, the rank of \(Z\). The problem of enumerating the number of distinct matroids on a fixed \(n\)-element set is only tractable for small values of \(n\). In view of this, upper and lower bounds have been sought on this number. Beginning in the 1970s, such bounds were given by various authors including Knuth and Piff. Observational data from that time had led to the conjecture that almost every matroid is paving, that is, has all sets of cardinality less than the rank of \(E\) being independent.

Dating back to the work of Plücker (1835), Kirkman (1847), and Steiner (1853), one of the oldest problems in combinatorics concerns the existence of a Steiner system, a family of \(t\)-element subsets, or blocks, of an \(n\)-element set \(E\) such that every \(d\)-element subset of \(E\) is in a unique block. These constraints impose certain natural divisibility conditions on the parameters \(n\), \(d\), and \(t\). A 2014 breakthrough result of Keevash proved that, when \(n\) is sufficiently large, these necessary conditions are also sufficient for the existence of a Steiner system. Subsequently, Keevash obtained asymptotic estimates on the number of Steiner systems.

A Steiner system on \(E\) yields a paving matroid by taking the independent sets to be all sets with at most \(d\) elements along with all \((d+1)\)-element sets that are not contained in a block. In the current paper, the authors prove an asymptotic estimate of the number of paving matroids of fixed rank. This yields an asymptotic estimate on the number of number of matroids of fixed rank exceeding three that mimics Keevash’s estimate.