Enumerating matroids of fixed rank

zbMATH Open1355.05033arXiv1512.06655MaRDI QIDQ510313FDOQ510313

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

Publication date: 17 February 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: It has been conjectured that asymptotically almost all matroids are sparse paving, i.e. that $s(n)simm(n)$, where $m(n)$ denotes the number of matroids on a fixed groundset of size $n$, and $s(n)$ the number of sparse paving matroids. In an earlier paper, we showed that $logs(n)simlogm(n)$. The bounds that we used for that result were dominated by matroids of rank $rapproxn/2$. In this paper we consider the relation between the number of sparse paving matroids $s(n,r)$ and the number of matroids $m(n,r)$ on a fixed groundset of size $n$ of fixed rank $r$. In particular, we show that $logs(n,r)simlogm(n,r)$ whenever $rge3$, by giving asymptotically matching upper and lower bounds. Our upper bound on $m(n,r)$ relies heavily on the theory of matroid erections as developed by Crapo and Knuth, which we use to encode any matroid as a stack of paving matroids. Our best result is obtained by relating to this stack of paving matroids an antichain that completely determines the matroid. We also obtain that the collection of essential flats and their ranks gives a concise description of matroids.

Full work available at URL: https://arxiv.org/abs/1512.06655

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On the number of matroids compared to the number of sparse paving matroids
• On the number of sparse paving matroids
• On the number of matroids
• On the number of bases of almost all matroids
• On the number of matroids

zbMATH Keywords

asymptotic enumerationmatroid theory

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Asymptotic enumeration (05A16) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Some intersection theorems for ordered sets and graphs
• Counting designs
• Title not available (Why is that?)
• Monotone Boolean functions
• A note on the random greedy independent set algorithm
• Title not available (Why is that?)
• On the number of sparse paving matroids
• On the asymptotic proportion of connected matroids
• On the number of matroids
• Lower bounds for constant weight codes
• A Catalogue of Combinatorial Geometries
• On the Number of Combinatorial Geometries
• Title not available (Why is that?)
• On the number of matroids compared to the number of sparse paving matroids
• An entropy argument for counting matroids
• On the Foundations of Combinatorial Theory II. Combinatorial Geometries
• Matroid erection and duality
• Random matroids
• Title not available (Why is that?)

Cited In (16)

• Title not available (Why is that?)
• On the Complexity of Some Enumeration Problems for Matroids
• The number of partial Steiner systems and d-partitions
• Basis-exchange properties of sparse paving matroids
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• On the number of matroids compared to the number of sparse paving matroids
• On the number of matroids
• On the number of matroids on a finite set
• Truncated Boolean representable simplicial complexes
• On the number of matroids
• On the Wilson monoid of a pairwise balanced design
• On the number of sparse paving matroids
• Quotients of uniform positroids
• Asymptotics of symmetry in matroids
• Counting matroids in minor-closed classes
• Almost every matroid has an \(M(K_4)\)- or a \(\mathcal{W}^3\)-minor

This page was built for publication: Enumerating matroids of fixed rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510313)