Enumerating Matroids and Linear Spaces

Matthew Kwan; Ashwin Sah; Mehtaab Sawhney

doi:10.5802/crmath.423

Combinatoire

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.

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 :

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

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@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/

Bibliographie
Cité par

[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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Coloration des graphes de reines

Michel Vasquez

C. R. Math (2006)

Refinements and Symmetries of the Morris identity for volumes of flow polytopes

Alejandro H. Morales; William Shi

C. R. Math (2021)

Möbius inversion formula for the trace group

Anne Bouillard; Jean Mairesse

C. R. Math (2004)