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

preprint2014arXivOpen access

Abstract

It has been conjectured that sparse paving matroids will eventually predominate in any asymptotic enumeration of matroids, i.e. that lim⁡n→∞sn/mn=1\lim_{n\rightarrow\infty} s_n/m_n = 1, where mnm_n denotes the number of matroids on nn elements, and sns_n the number of sparse paving matroids. In this paper, we show that lim⁡n→∞log⁡snlog⁡mn=1.\lim_{n\rightarrow \infty}\frac{\log s_n}{\log m_n}=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 some β>0β> 0, asymptotically almost all matroids on nn elements have rank in the range n/2±βnn/2 \pm β\sqrt{n}.

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.