Measuring Depth of Matroids
This work provides a systematic unification of scattered depth concepts in matroid theory, which is incremental but important for researchers in combinatorial optimization and integer programming.
The authors tackled the problem of unifying various recursive depth parameters for matroids and matrices by proposing a general framework that yields eight depth measures, proving their properties and relationships, and showing that six are functionally inequivalent while two align with existing notions like matroid branch-depth and tree-depth.
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.