On the number of bases of almost all matroids

Rudi Pendavingh, Jorn van der Pol

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
33 Downloads (Pure)

Abstract

For a matroid M of rank r on n elements, let b(M) denote the fraction of bases of M among the subsets of the ground set with cardinality r. We show that Ω(1/n)≤1−b(M)≤O(log(n)3/n)asn→∞ for asymptotically almost all matroids M on n elements. We derive that asymptotically almost all matroids on n elements (1) have a U k,2k-minor, whenever k≤O(log(n)), (2) have girth ≥Ω(log(n)), (3) have Tutte connectivity ≥Ω(log(n)), and (4) do not arise as the truncation of another matroid. Our argument is based on a refined method for writing compressed descriptions of any given matroid, which allows bounding the number of matroids in a class relative to the number of sparse paving matroids.

Original languageEnglish
Pages (from-to)955–985
Number of pages31
JournalCombinatorica
Volume38
Issue number4
DOIs
Publication statusPublished - 1 Aug 2018

Fingerprint

Dive into the research topics of 'On the number of bases of almost all matroids'. Together they form a unique fingerprint.

Cite this