Problem of the Week
Hilton Memorial Lecture
We consider the number of matroids on an n-element ground set. For fixed rank, we obtain asymptotically precise upper and lower bounds, provided the rank is at least 4 (a gap remains for rank-3 matroids).
Of particular interest are sparse paving matroids. This is a class of well-behaved matroids that is closely related to both Steiner systems and matchings in hypergraphs. Existing enumeration methods (Linial-Luria, Bennett-Bohman) that work in those settings can be adapted to give bounds for sparse paving matroids as well. A combinatorial argument then extends these bounds to the broader class of paving matroids, and thence to general matroids.
This is joint work with Remco van der Hofstad and Rudi Pendavingh (TU/e).