Shifted and Threshold Matroids
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916923756773376 |
|---|---|
| author | Partida, Ethan |
| author_facet | Partida, Ethan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_07810 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Shifted and Threshold Matroids Partida, Ethan Combinatorics 05B35 (Primary) 05C65, 90C27 (Secondary) 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. |
| title | Shifted and Threshold Matroids |
| topic | Combinatorics 05B35 (Primary) 05C65, 90C27 (Secondary) |
| url | https://arxiv.org/abs/2408.07810 |