Enumerating matroids of fixed rank

MaRDI QIDQ510313zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1512.06655, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p8

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

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)

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.

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

Cites work

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

Cited in

(16)

• scientific article; zbMATH DE number 6515828 (Why is no real title available?)
• On the Complexity of Some Enumeration Problems for Matroids
• Basis-exchange properties of sparse paving matroids
• The number of partial Steiner systems and d-partitions
• 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)