تقرير
Branch-depth is minor closure of contraction-deletion-depth
| العنوان: | Branch-depth is minor closure of contraction-deletion-depth |
|---|---|
| المؤلفون: | Briański, Marcin, Kráľ, Daniel, Pekárková, Kristýna |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2402.16215 |
| رقم الأكسشن: | edsarx.2402.16215 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!