Measuring Depth of Matroids
2026-04-06 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study different ways to measure the 'depth' or complexity of mathematical objects called matroids and matrices. They create a general system that defines eight depth measures, exploring how these relate to known concepts like matroid branch-depth and tree-width. They find that most of these measures are distinct, though some are equivalent to existing ones, and show that these depth measures behave the same for both matroids and matrices over any field. Their work helps connect and clarify several scattered ideas in this area, also comparing these new matroid depth measures with classic graph depth concepts.
matroidmatrixdepth measurebranch-depthtree-widthtree-depthinteger programmingrecursive parametersgraph depthfield
Authors
Jakub Balabán, Petr Hliněný, Jan Jedelský, Kristýna Pekárková
Abstract
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.