Enumerating Matroids and Linear Spaces

Matthew Kwan; Ashwin Sah; Mehtaab Sawhney

doi:10.5802/crmath.423

Combinatorics

Enumerating Matroids and Linear Spaces

Matthew Kwan ¹; Ashwin Sah ²; Mehtaab Sawhney ²

¹ Institute of Science and Technology Austria, 3400 Klosterneuburg, Austria
² Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Comptes Rendus. Mathématique, Volume 361 (2023), pp. 565-575.

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 ${(c n + o (n))}^{n^{2} / 6}$ , where $c = e^{\sqrt{3} / 2 - 3} (1 + \sqrt{3}) / 2$ . This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: there are exact formulas for enumeration of rank-1 and rank-2 matroids, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant $r \geq 4$ there are ${(e^{1 - r} n + o (n))}^{n^{r - 1} / r!}$ rank- $r$ matroids on a ground set of size $n$ .

Received: 2021-12-14
Accepted: 2022-09-12
Published online: 2023-02-01

DOI: 10.5802/crmath.423

Author's affiliations:

Matthew Kwan ¹; Ashwin Sah ²; Mehtaab Sawhney ²

¹ Institute of Science and Technology Austria, 3400 Klosterneuburg, Austria
² Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CRMATH_2023__361_G2_565_0,
     author = {Matthew Kwan and Ashwin Sah and Mehtaab Sawhney},
     title = {Enumerating {Matroids} and {Linear} {Spaces}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {565--575},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {361},
     year = {2023},
     doi = {10.5802/crmath.423},
     language = {en},
}

TY  - JOUR
AU  - Matthew Kwan
AU  - Ashwin Sah
AU  - Mehtaab Sawhney
TI  - Enumerating Matroids and Linear Spaces
JO  - Comptes Rendus. Mathématique
PY  - 2023
SP  - 565
EP  - 575
VL  - 361
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.423
LA  - en
ID  - CRMATH_2023__361_G2_565_0
ER  -

%0 Journal Article
%A Matthew Kwan
%A Ashwin Sah
%A Mehtaab Sawhney
%T Enumerating Matroids and Linear Spaces
%J Comptes Rendus. Mathématique
%D 2023
%P 565-575
%V 361
%I Académie des sciences, Paris
%R 10.5802/crmath.423
%G en
%F CRMATH_2023__361_G2_565_0

Matthew Kwan; Ashwin Sah; Mehtaab Sawhney. Enumerating Matroids and Linear Spaces. Comptes Rendus. Mathématique, Volume 361 (2023), pp. 565-575. doi : 10.5802/crmath.423. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.423/

References
Cited by

[1] Dragan M. Acketa On the enumeration of matroids of rank 2, Zb. Rad., Prir.-Mat. Fak., Univ. Novom Sadu, Ser. Mat., Volume 8 (1978), pp. 83-90 | Zbl

[2] Nikhil Bansal; Rudi A. Pendavingh; Jorn G. van der Pol On the number of matroids, Combinatorica, Volume 35 (2015) no. 3, pp. 253-277 | DOI | Zbl

[3] Lynn Margaret Batten; Albrecht Beutelspacher The theory of finite linear spaces, Cambridge University Press, 1993 | DOI | Zbl

[4] W. M. B. Dukes On the number of matroids on a finite set, Sémin. Lothar. Comb., Volume 51 (2004), B51g | Zbl

[5] Remco van der Hofstad; Rudi Pendavingh; Jorn G. van der Pol The number of partial Steiner systems and d-partitions, Adv. Comb., Volume 2022 (2022) | DOI

[6] Svante Janson; Tomasz Łuczak; Andrzej Rucinski Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, 2000 | DOI | Zbl

[7] Peter Keevash Counting designs, J. Eur. Math. Soc. (JEMS), Volume 20 (2018) no. 4, pp. 903-927 | DOI | Zbl

[8] Peter Keevash The existence of designs (2019) (https://arxiv.org/abs/1401.3665)

[9] Donald E. Knuth The asymptotic number of geometries, J. Combinatorial Theory Ser. A, Volume 16 (1974), pp. 398-400 | DOI | Zbl

[10] Matthew Kwan Almost all Steiner triple systems have perfect matchings, Proc. Lond. Math. Soc., Volume 121 (2020) no. 6, pp. 1468-1495 | DOI | Zbl

[11] Nathan Linial; Zur Luria An upper bound on the number of Steiner triple systems, Random Structures Algorithms, Volume 43 (2013) no. 4, pp. 399-406 | DOI | Zbl

[12] Brendan D. McKay; Nicholas C. Wormald Wormald, Asymptotic enumeration by degree sequence of graphs of high degree, European J. Combin., Volume 11 (1990) no. 6, pp. 565-580 | DOI | Zbl

[13] OEIS WikiContributors Index to OEIS: Matroids, sequences related to, 2022 (http://oeis.org/wiki/Index_to_ OEIS:_Section_Mat#matroid)

[14] James Oxley Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford University Press, Oxford, 2011 | DOI | Zbl

[15] Rudi A. Pendavingh; Jorn G. van der Pol Enumerating matroids of fixed rank, Electron. J. Combin., Volume 24 (2017) no. 1, 1.8 | Zbl

[16] M. J. Piff An upper bound for the number of matroids, J. Combinatorial Theory Ser. B, Volume 14 (1973), pp. 241-245 | DOI | Zbl

[17] M. J. Piff; Dominic J. A. Welsh The number of combinatorial geometries, Bull. London Math. Soc., Volume 3 (1971), pp. 55-56 | DOI | Zbl

[18] Jorn G. van der Pol Large matroids: enumeration and typical properties, Ph. D. Thesis, Mathematics and Computer Science, Technische Universiteit Eindhoven, Netherlands (2017)

[19] Ernest E. Shult Points and lines. Characterizing the classical geometries, Universitext, Springer, 2011 | DOI | Zbl

[20] Dominic J. A. Welsh Matroid theory, London Mathematical Society Monographs, 8, Academic Press [Harcourt Brace Jovanovich, Publishers], 1976 | Zbl

Cited by Sources:

Comments - Policy