Measuring Depth of Matroids
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911651474702336 |
|---|---|
| author | Balabán, Jakub Hliněný, Petr Jedelský, Jan Pekárková, Kristýna |
| author_facet | Balabán, Jakub Hliněný, Petr Jedelský, Jan Pekárková, Kristýna |
| contents | Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursive depth parameters for matrices and matroids, aiming to unify recently introduced and scattered concepts. We propose a general framework that naturally yields eight different depth measures for matroids, prove their fundamental properties and relationships, and relate them to two established notions in the field: matroid branch-depth and a newly introduced natural depth counterpart of matroid tree-width. In particular, we show that six of our eight measures are mutually functionally inequivalent, and among these, one is functionally equivalent to matroid branch-depth and another to matroid tree-depth. Importantly, we also prove that these depth measures coincide on matroids and on matrices over any field, which is (somehow surprisingly) not a trivial task. Finally, we provide a comparison between the matroid parameters and classical depth measures of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04896 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Measuring Depth of Matroids Balabán, Jakub Hliněný, Petr Jedelský, Jan Pekárková, Kristýna Combinatorics Discrete Mathematics 05B35 Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursive depth parameters for matrices and matroids, aiming to unify recently introduced and scattered concepts. We propose a general framework that naturally yields eight different depth measures for matroids, prove their fundamental properties and relationships, and relate them to two established notions in the field: matroid branch-depth and a newly introduced natural depth counterpart of matroid tree-width. In particular, we show that six of our eight measures are mutually functionally inequivalent, and among these, one is functionally equivalent to matroid branch-depth and another to matroid tree-depth. Importantly, we also prove that these depth measures coincide on matroids and on matrices over any field, which is (somehow surprisingly) not a trivial task. Finally, we provide a comparison between the matroid parameters and classical depth measures of graphs. |
| title | Measuring Depth of Matroids |
| topic | Combinatorics Discrete Mathematics 05B35 |
| url | https://arxiv.org/abs/2604.04896 |