On the number of matroids compared to the number of sparse paving matroids

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

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
66 Downloads (Pure)

Abstract

t has been conjectured that sparse paving matroids will eventually predominate in any asymptotic enumeration of matroids, i.e. that limn→∞sn/mn=1limn→∞sn/mn=1, where mnmn denotes the number of matroids on nn elements, and snsn the number of sparse paving matroids. In this paper, we show that limn→∞logsnlogmn=1. limn→∞log⁡snlog⁡mn=1. We prove this by arguing that each matroid on nn elements has a faithful description consisting of a stable set of a Johnson graph together with a (by comparison) vanishing amount of other information, and using that stable sets in these Johnson graphs correspond one-to-one to sparse paving matroids on nn elements. As a consequence of our result, we find that for all β>ln22−−−−√=0.5887⋯β>ln⁡22=0.5887⋯, asymptotically almost all matroids on nn elements have rank in the range n/2±βn−−√n/2±βn.
Original languageEnglish
Pages (from-to)1-17
Number of pages17
JournalThe Electronic Journal of Combinatorics
Volume22
Issue number2
Publication statusPublished - 15 Jun 2015

Keywords

  • Asymptotic enumeration
  • Matroid theory

Fingerprint

Dive into the research topics of 'On the number of matroids compared to the number of sparse paving matroids'. Together they form a unique fingerprint.

Cite this