2016/02/15 by Pendavingh, Rudi, van der Pol, Jorn
#05A16 #05B35 #94A17 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1602.04763
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) as n→ ∞ for asymptotically almost all matroids M on n elements. We derive that asymptotically almost all matroids on n elements (1) have a Uk,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.