Shifted and Threshold Matroids
arXiv:2408.07810 · doi:10.1016/j.dam.2025.08.038
Abstract
We characterize the class of threshold matroids by the structure of their defining bases. We also give an example of a shifted matroid which is not threshold, answering a question of Deza and Onn. We conclude by exploring consequences of our characterization of threshold matroids: We give a formula for the number of isomorphism classes of threshold matroids on a ground set of size n. This enumeration shows that almost all shifted matroids are not threshold. We also present a polynomial-time algorithm to check if a matroid is threshold and provide alternative and simplified proofs of some of the main results of Deza and Onn.
18 pages, 2 figures, Final version accepted in Discrete Applied Mathematics