Paving matroid

From Egres Open
Jump to: navigation, search

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.


  1. D.E. Knuth, The asymptotic number of geometries, DOI link
  2. D. Mayhew, M. Newman, D. Welsh, and G. Whittle, On the asymptotic proportion of connected matroids, DOI link, author link
  3. N. Bansal, R.A. Pendavingh, J.G. van der Pol, On the number of matroids, arXiv link