Counting matroids in minor-closed classes

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

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
78 Downloads (Pure)

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 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 an M(K4)-minor which asymptotically matches the best known lower bound on the number of all matroids, due to Knuth.

Original languageEnglish
Pages (from-to)126-147
Number of pages22
JournalJournal of Combinatorial Theory, Series B
Volume111
DOIs
Publication statusPublished - 1 Mar 2015

Keywords

  • Algorithmic complexity
  • Asymptotic enumeration
  • Excluded minor
  • Matroid

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

  • Cite this