In the mathematical theory of matroids, a paving matroid is a matroid in which every circuit has size at least as large as the matroid's rank. In a matroid of rank r {\displaystyle r} every circuit has size at most r + 1 {\displaystyle r+1} , so it is equivalent to define paving matroids as the matroids in which the size of every circuit belongs to the set { r , r + 1 } {\displaystyle \{r,r+1\}} . It has been conjectured that almost all matroids are paving matroids.
Examples Every simple matroid of rank three is a paving matroid; for instance this is true of the Fano matroid. The Vámos matroid provides another example, of rank four. Uniform matroids of rank r {\displaystyle r} have the property that every circuit is of length exactly r + 1 {\displaystyle r+1} and hence are all paving matroids; the converse does not hold, for example, the cycle matroid of the complete graph K 4 {\displaystyle K_{4}} is paving but not uniform. A Steiner system S ( t , k , v ) {\displaystyle S(t,k,v)} is a pair ( S , D ) {\displaystyle (S,{\mathcal {D}})} where S {\displaystyle S} is a finite set of size v {\displaystyle v} and D {\displaystyle {\mathcal {D}}} is a family of k {\displaystyle k} -element subsets of S {\displaystyle S} with the property that every t {\displaystyle t} distinct elements of S {\displaystyle S} are contained in exactly one set in D {\displaystyle {\mathcal {D}}} . The elements of D {\displaystyle {\mathcal {D}}} form a t {\displaystyle t} -partition of S {\displaystyle S} and hence are the hyperplanes of a paving matroid on S {\displaystyle S} .
d-Partitions If a paving matroid has rank d + 1 {\displaystyle d+1} , then its hyperplanes form a set system known as a d {\displaystyle d} -partition. A family of two or more sets F {\displaystyle {\mathcal {F}}} forms a d {\displaystyle d} -partition if every set in F {\displaystyle {\mathcal {F}}} has size at least d {\displaystyle d} and every d {\displaystyle d} -element subset of ⋃ F {\displaystyle \bigcup {\mathcal {F}}} is a subset of exactly one set in F {\displaystyle {\mathcal {F}}} . Conversely, if F {\displaystyle {\mathcal {F}}} is a d {\displaystyle d} -partition, then it can be used to define a paving matroid on E = ⋃ F {\displaystyle E=\bigcup {\mathcal {F}}} for which F {\displaystyle {\mathcal {F}}} is the set of hyperplanes. In this matroid, a subset I {\displaystyle I} of E {\displaystyle E} is independent whenever either | I | ≤ d {\displaystyle |I|\leq d} or | I | = d + 1 {\displaystyle |I|=d+1} and I {\displaystyle I} is not a subset of any set in F {\displaystyle {\mathcal {F}}} .
Combinatorial enumeration Combinatorial enumeration of the simple matroids on up to nine elements has shown that a large fraction of them are also paving matroids. On this basis, it has been conjectured that almost all matroids are paving matroids. More precisely, according to this conjecture, the limit, as n goes to infinity, of the ratio between the number of paving matroids and the number of all matroids should equal one. If so, the same statement can be made for the sparse paving matroids, matroids that are both paving and dual to a paving matroid. Although this remains open, a similar statement on the asymptotic ratio of the logarithms of the numbers of matroids and sparse paving matroids has been proven.
… excerpt ends here. Continue reading the full article.
