Enumerating Matroids and Linear Spaces

Kwan, Matthew; Sah, Ashwin; Sawhney, Mehtaab

doi:10.5802/crmath.423

Combinatoire

Enumerating Matroids and Linear Spaces

Kwan, Matthew ¹ ; Sah, Ashwin ² ; Sawhney, Mehtaab ²

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

Comptes Rendus. Mathématique, Tome 361 (2023) no. G2, pp. 565-575

Résumé

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$ .

Reçu le : 2021-12-14
Accepté le : 2022-09-12
Publié le : 2023-02-01

DOI : 10.5802/crmath.423

Affiliations des auteurs :

Kwan, Matthew ¹ ; Sah, Ashwin ² ; Sawhney, Mehtaab ²

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

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

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

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

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

Kwan, Matthew; Sah, Ashwin; Sawhney, Mehtaab. Enumerating Matroids and Linear Spaces. Comptes Rendus. Mathématique, Tome 361 (2023) no. G2, pp. 565-575. doi: 10.5802/crmath.423

Bibliographie
Cité par

[1] Acketa, Dragan M. 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] Bansal, Nikhil; Pendavingh, Rudi A.; van der Pol, Jorn G. On the number of matroids, Combinatorica, Volume 35 (2015) no. 3, pp. 253-277 | DOI | Zbl

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

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

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

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

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

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

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

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

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

[12] McKay, Brendan D.; Wormald, Nicholas C. 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] Oxley, James Matroid theory, Oxford Graduate Texts in Mathematics, 21, Oxford University Press, Oxford, 2011 | DOI | Zbl

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

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

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

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

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

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

Cité par Sources :