Counting matroids in minor-closed classes

R.A. Pendavingh, J.G. Pol, van der

Research output: Book/ReportReportAcademic

Abstract

A flat cover is a collection of flats identifying the non-bases of a matroid. We introduce the notion of cover complexity, the minimal size of such a flat cover, as a measure for the complexity of a matroid, and present bounds on the number of matroids on $n$ elements whose cover complexity is bounded. We apply cover complexity to show that the class of matroids without an $N$-minor is asymptotically small in case $N$ is one of the sparse paving matroids $U_{2,k}$, $U_{3,6}$, $P_6$, $Q_6$, or $R_6$, thus confirming a few special cases of a conjecture due to Mayhew, Newman, Welsh, and Whittle. On the other hand, we show a lower bound on the number of matroids without $M(K_4)$-minor which asymptoticaly matches the best known lower bound on the number of all matroids, due to Knuth.
Original languageEnglish
Publishers.n.
Number of pages13
Publication statusPublished - 2013

Publication series

NamearXiv.org
Volume1302.1315 [math.CO]

Fingerprint

Dive into the research topics of 'Counting matroids in minor-closed classes'. Together they form a unique fingerprint.

Cite this