Paving matroid
From Egres Open
A matroid M is called paving if every set of size r(M)-1 is independent. It is called sparse paving if in addition every circuit of size r(M) is closed. The importance of (sparse) paving matroids stems from their large number: lower bounds on the number of matroids are obtained by counting sparse paving matroids, see e.g. Knuth [1]. In fact, Mayhew et al. [2] conjecture that if [math]m_n[/math] is the number of matroids and [math]s_n[/math] is the number of sparse paving matroids on [math]n[/math] elements, then [math]\lim_{n \to \infty} \frac{m_n}{s_n} =1[/math]. Progress towards this conjecture has been made in [3].
See also Wikipedia:Paving matroid.
References
- ↑ D.E. Knuth, The asymptotic number of geometries, DOI link
- ↑ D. Mayhew, M. Newman, D. Welsh, and G. Whittle, On the asymptotic proportion of connected matroids, DOI link, author link
- ↑ N. Bansal, R.A. Pendavingh, J.G. van der Pol, On the number of matroids, arXiv link
