Enumerating matroids of fixed rank

R. Pendavingh, J. van der Pol

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
38 Downloads (Pure)

Abstract

It has been conjectured that asymptotically almost all matroids are sparse paving, i.e. that~s(n)∼m(n)s(n)∼m(n), where m(n)m(n) denotes the number of matroids on a fixed groundset of size nn, and s(n)s(n) the number of sparse paving matroids. In an earlier paper, we showed that logs(n)∼logm(n)log⁡s(n)∼log⁡m(n). The bounds that we used for that result were dominated by matroids of rank r≈n/2r≈n/2. In this paper we consider the relation between the number of sparse paving matroids s(n,r)s(n,r) and the number of matroids m(n,r)m(n,r) on a fixed groundset of size nn of fixed rank rr. In particular, we show that logs(n,r)∼logm(n,r)log⁡s(n,r)∼log⁡m(n,r) whenever r≥3r≥3, by giving asymptotically matching upper and lower bounds.

Our upper bound on m(n,r)m(n,r) relies heavily on the theory of matroid erections as developed by Crapo and Knuth, which we use to encode any matroid as a stack of paving matroids. Our best result is obtained by relating to this stack of paving matroids an antichain that completely determines the matroid. We also obtain that the collection of essential flats and their ranks gives a concise description of matroids.
Original languageEnglish
Article numberP1.8
Pages (from-to)1-28
JournalThe Electronic Journal of Combinatorics
Volume24
Issue number1
Publication statusPublished - 20 Jan 2017

Keywords

  • Matroid theory
  • Asymptotic enumeration

Fingerprint Dive into the research topics of 'Enumerating matroids of fixed rank'. Together they form a unique fingerprint.

Cite this