2013/02/06 by Rudi Pendavingh, Pendavingh, R. A., J.G. van der Pol +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1302.1315
openalex publication_date 2013/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 U2,k, U3,6, P6, Q6, or R6, 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(K4)-minor which asymptoticaly matches the best known lower bound on the number of all matroids, due to Knuth.