Branch-depth is minor closure of contraction-deletion-depth
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909120095846400 |
|---|---|
| author | Briański, Marcin Kráľ, Daniel Pekárková, Kristýna |
| author_facet | Briański, Marcin Kráľ, Daniel Pekárková, Kristýna |
| contents | The notion of branch-depth for matroids was introduced by DeVos, Kwon and Oum as the matroid analogue of the tree-depth of graphs. The contraction-deletion-depth, another tree-depth like parameter of matroids, is the number of recursive steps needed to decompose a matroid by contractions and deletions to single elements. Any matroid with contraction-deletion-depth at most d has branch-depth at most d. However, the two notions are not functionally equivalent as contraction-deletion-depth of matroids with branch-depth two can be arbitrarily large.
We show that the two notions are functionally equivalent for representable matroids when minor closures are considered. Namely, an F-representable matroid has small branch-depth if and only if it is a minor of an F-representable matroid with small contraction-deletion-depth. This implies that any class of F-representable matroids has bounded branch-depth if and only if it is a subclass of the minor closure of a class of F-representable matroids with bounded contraction-deletion-depth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16215 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Branch-depth is minor closure of contraction-deletion-depth Briański, Marcin Kráľ, Daniel Pekárková, Kristýna Combinatorics Discrete Mathematics The notion of branch-depth for matroids was introduced by DeVos, Kwon and Oum as the matroid analogue of the tree-depth of graphs. The contraction-deletion-depth, another tree-depth like parameter of matroids, is the number of recursive steps needed to decompose a matroid by contractions and deletions to single elements. Any matroid with contraction-deletion-depth at most d has branch-depth at most d. However, the two notions are not functionally equivalent as contraction-deletion-depth of matroids with branch-depth two can be arbitrarily large. We show that the two notions are functionally equivalent for representable matroids when minor closures are considered. Namely, an F-representable matroid has small branch-depth if and only if it is a minor of an F-representable matroid with small contraction-deletion-depth. This implies that any class of F-representable matroids has bounded branch-depth if and only if it is a subclass of the minor closure of a class of F-representable matroids with bounded contraction-deletion-depth. |
| title | Branch-depth is minor closure of contraction-deletion-depth |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2402.16215 |