Enumerating matroids, linear spaces and clique-decompositions
Thu
17
Feb
Thursday 17 February, 2022at 14:15 - 15:00
Zoom
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, for an explicit constant c ≈ 0.162. 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 r ≥ 4 there are (e1−rn+o(n))n^{r−1}/r! rank-r matroids on a ground set of size n. The proof comes down to counting clique-decompositions of the complete graph; to this end we introduce some new counting techniques, using quasirandomness instead of the so-called entropy method that is common in this area.