Enumerating Matroids and Linear Spaces

DOI10.5802/CRMATH.423MaRDI QIDQ6385031arXivFDO

Authors Matthew Kwan, Ashwin Sah, Mehtaab Sawhney

Publication date 7 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.5802/CRMATH.423

Mathematics Subject Classification ID

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

arXiv classification

math.CO

Abstract: We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(cn+o(n){)}^{n^2/6}$, where $c=e^{sqrt3/2-3}(1+sqrt3)/2$. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: the numbers of rank-1 and rank-2 matroids on a ground set of size $n$ have exact representations in terms of well-known combinatorial functions, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant $rge4$ there are $(e^{1-r}n+o(n){)}^{n^{r-1}/r!}$ rank-$r$ matroids on a ground set of size $n$. In our proof, we introduce a new approach for bounding the number of clique decompositions of a complete graph, using quasirandomness instead of the so-called entropy method that is common in this area.

This page was built for publication: Enumerating Matroids and Linear Spaces

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