On the number of bases of almost all matroids

preprint2016arXivOpen access

Abstract

For a matroid MM of rank rr on nn elements, let b(M)b(M) denote the fraction of bases of MM among the subsets of the ground set with cardinality rr. We show that Ω(1/n)≤1−b(M)≤O(log⁡(n)3/n) as n→∞Ω(1/n)\leq 1-b(M)\leq O(\log(n)^3/n)\text{ as }n\rightarrow \infty for asymptotically almost all matroids MM on nn elements. We derive that asymptotically almost all matroids on nn elements (1) have a Uk,2kU_{k,2k}-minor, whenever k≤O(log⁡(n))k\leq O(\log(n)), (2) have girth ≥Ω(log⁡(n))\geq Ω(\log(n)), (3) have Tutte connectivity ≥Ω(log⁡(n))\geq Ω(\sqrt{\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.