A method to construct all the paving matroids over a finite set (Q2155830)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A method to construct all the paving matroids over a finite set |
scientific article |
Statements
A method to construct all the paving matroids over a finite set (English)
0 references
15 July 2022
0 references
Paving matroids were defined in [\textit{J. Hartmanis}, Can. J. Math. 11, 97--106 (1959; Zbl 0089.37002)] through the concept of \(d\)-partitions in number theory. Paving matroids play a significant role in computer science via greedy algorithms and the matroid oracles [\textit{C. Heunen} and \textit{V. Patta}, Appl. Categ. Struct. 26, No. 2, 205--237 (2018; Zbl 1403.18002)]. This paper aims to give a characterization of paving matroids leading to a concrete construction of their hyperplances and to an algorithm for finding them. A counterexample to a characterization of paving matroids by \textit{J. G. Oxley} [Matroid theory. 2nd ed. Oxford: Oxford University Press (2011; Zbl 1254.05002), 1.3.10] is given. A simple proof of Rota's basis conjecture [\textit{G.-C. Rota}, Mitt. Dtsch. Math.-Ver. 6, No. 2, 45--52 (1998; Zbl 1288.00005)] is given for the case of sparse-paving matroids and for the case of paving matroids of rank \(r\) on a set of cardinality \(n\leq2r\).
0 references
simple matroid
0 references
paving matroid
0 references
sparse-paving matroid
0 references
lattice
0 references
hyperplanes of a matroid
0 references
circuits of a matroid
0 references
Rota's basis conjecture
0 references
0 references