arxiv: 2604.04896 · v2 · submitted 2026-04-06 · 🧮 math.CO · cs.DM

Recognition: 2 theorem links

· Lean Theorem

Measuring Depth of Matroids

Jakub Balab\'an , Petr Hlin\v{e}n\'y , Jan Jedelsk\'y , Krist\'yna Pek\'arkov\'a

Authors on Pith no claims yet

Pith reviewed 2026-05-10 19:38 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05B35

keywords matroid depthbranch-depthtree-depthrecursive parametersmatrix representationsmatroid minorsinteger programminggraph depth measures

0 comments

The pith

A recursive framework generates eight depth measures for matroids, six of which are functionally inequivalent, with two matching established parameters.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a general framework for defining recursive depth parameters on matroids and matrices. This framework produces eight specific depth measures whose basic properties and relationships are established. The authors prove that six of these measures are mutually functionally inequivalent, while one is equivalent to matroid branch-depth and another to a newly defined tree-depth parameter. They further show that all the measures yield identical values when applied directly to matroids or to their matrix representations over any field. This unification matters because depth controls the complexity of algorithms for structured integer programs, and agreement across representations removes a potential source of inconsistency in applications.

Core claim

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.

What carries the argument

The general recursive framework that produces eight depth measures by repeated application of defined reduction rules to matroids or matrices.

If this is right

Branch-depth and the tree-depth counterpart arise naturally as two of the eight measures inside the same framework.
Depth parameters can be computed from any matrix representation without first constructing the matroid.
The six inequivalent measures supply a strict hierarchy of structural restrictions for matroid problems.
Direct comparisons become possible between these matroid depths and the classical depth parameters already used on graphs.
The framework supplies a uniform language for studying how depth affects the tractability of block-structured integer programs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Parameterized algorithms whose running time depends on one of these depths could be transferred directly between the matroid and matrix views of the same input.
The same recursive pattern might be applied to other combinatorial objects such as hypergraphs or signed graphs to produce analogous depth hierarchies.
Empirical computation of the eight measures on families of random or structured matroids would reveal which ones are easiest to evaluate in practice.
If the measures remain distinct on graphic matroids, they would induce new width parameters for graphs that sit between existing ones.

Load-bearing premise

The specific recursive rules chosen for the framework define depth notions that remain meaningful and comparable across matroids and matrices.

What would settle it

A concrete matroid together with one of its matrix representations over a field such that the depth value obtained from the matroid definition differs from the depth value obtained from the matrix definition.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper sets up a recursive framework that produces eight matroid depth measures, proves six are functionally distinct, matches two to branch-depth and tree-depth, and shows the matroid and matrix versions agree over every field.

read the letter

The core contribution is a single recursive template that generates eight depth parameters on matroids. The authors prove basic properties, establish that six of the eight are pairwise functionally inequivalent, identify one as equivalent to matroid branch-depth and another to a natural tree-depth analogue, and show that the matroid and matrix versions coincide for any field. They close with a short comparison to classical graph depth measures. That coincidence result is the part that takes real work; the abstract flags it as non-trivial, and the stress-test note finds no internal inconsistency in the stated claims. The framework itself is a useful organizing device that ties together ideas from the recent ICALP papers on block-structured integer programming. The inequivalence proofs rest on separating examples, which appear to be the main technical content. If those examples are clean and the recursions are applied consistently, the distinctions hold. The choice of exactly these eight variants is driven by the recursion rules; a reader might still ask why other natural combinations were left out, but the inequivalence results make the distinctions concrete rather than arbitrary. No load-bearing circularity or hidden fitting is visible from the claims. This is solid, checkable work for matroid theorists and people who use depth or width parameters in combinatorial optimization. A specialist will get a clear map of how the new measures sit relative to branch-depth and tree-depth. I would send it to peer review; the results are specific enough that referees can verify the separations and the coincidence without needing to invent new machinery.

Referee Report

0 major / 3 minor

Summary. The paper introduces a general recursive framework that produces eight depth measures for matroids (and matrices). It proves their fundamental properties and interrelationships, establishes that six of the eight are pairwise functionally inequivalent, shows that one coincides with matroid branch-depth and another with a natural depth analogue of matroid tree-width (termed tree-depth), proves that the measures coincide when defined on matroids versus on matrices over an arbitrary field, and compares the resulting matroid parameters with classical depth measures on graphs. The work is motivated by connections to block-structured integer programming.

Significance. If the internal consistency of the recursive definitions and the correctness of the inequivalence, equivalence, and coincidence arguments hold, the paper supplies a unified and systematic treatment of depth parameters for matroids. The non-trivial proof that the measures agree on matroids and on matrices over every field, together with the explicit separating examples for inequivalence, strengthens the conceptual foundations and may facilitate applications in combinatorial optimization. The comparison with graph-theoretic depth notions is a useful bridge to existing literature.

minor comments (3)

[Abstract / Introduction] The abstract states that the measures 'coincide on matroids and on matrices over any field, which is (somehow surprisingly) not a trivial task,' yet the introduction does not preview the key technical obstacle that makes the coincidence non-obvious; a one-sentence indication of the difficulty (e.g., differing base cases or rank functions) would help readers.
[Section 3 (Framework definition)] The recursive definitions of the eight measures are presented without an accompanying diagram or table that cross-references the eight combinations of recursion rules; such a table would clarify the parameter space and make the subsequent inequivalence proofs easier to follow.
[Final comparison section] The comparison with classical graph depth measures in the final section is brief; adding a short table that lists the matroid parameters alongside their graph counterparts (and notes which graph measures they generalize) would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the thorough and positive review of our manuscript. The recommendation for minor revision is appreciated, and we will make the necessary adjustments in the revised version. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; new recursive framework and proofs are self-contained

full rationale

The paper defines a general recursive framework that produces eight depth measures, then proves their basic properties, pairwise functional inequivalences (via explicit separating examples), and functional equivalences to branch-depth and tree-depth through direct arguments. It further proves coincidence between the matroid and matrix versions over any field. These steps rely on the internal consistency of the chosen recursions and new combinatorial arguments rather than reducing to prior inputs by construction. The ICALP 2020/2022 citations supply only motivational context for the connections to integer programming; they are not invoked to justify the framework definitions, the inequivalence claims, or the coincidence proofs. No self-definitional loops, fitted parameters renamed as predictions, ansatz smuggling, or load-bearing uniqueness theorems from self-citations appear in the derivation chain. The results are therefore independent of the cited prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Claims rest on standard matroid axioms and the specific recursive constructions introduced; no free parameters or invented physical entities appear.

axioms (1)

standard math Matroids satisfy the standard independence axioms (hereditary and augmentation properties)
All depth measures are defined recursively using matroid independence and rank functions.

invented entities (1)

Eight recursive depth measures no independent evidence
purpose: To provide a unified set of depth parameters for matroids and matrices
Newly defined within the proposed framework; no external falsifiable predictions are stated in the abstract.

pith-pipeline@v0.9.0 · 5474 in / 1309 out tokens · 51994 ms · 2026-05-10T19:38:49.632611+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat induction and embed_strictMono unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Definition 4.6: γδ-depth recursion via c/d/c*/d* transformations; eight measures; functional equivalences in Theorem 3.5 / Figure 2; coincidence of matroid vs matrix versions (Prop 5.25, 5.27)
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking (D=3 forcing) unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 5.11: c*d*-depth ~ branch-depth (quadratic); Theorem 5.20: c*-depth ~ matroid tree-depth

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

[1]

Branch-depth is minor closure of contraction-deletion-depth

Marcin Bria\'nski, Petr Hlin e n \' y , Daniel Kr \' a l', and Krist \' y na Pek \' a rkov \' a . Branch-depth is minor closure of contraction-deletion-depth. In preparation , 2026

2026
[2]

Characterization of matrices with bounded graver bases and depth parameters and applications to integer programming

Marcin Bria\'nski, Martin Kouteck \' y , Daniel Kr \' a l', Krist \' y na Pek \' a rkov \' a , and Felix Schr \" o der. Characterization of matrices with bounded graver bases and depth parameters and applications to integer programming. In 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France , vo...

work page doi:10.4230/lipics.icalp.2022.29 2022
[3]

Characterization of matrices with bounded graver bases and depth parameters and applications to integer programming

Marcin Bria\'nski, Martin Kouteck \' y , Daniel Kr \' a l', Krist \' y na Pek \' a rkov \' a , and Felix Schr \" o der. Characterization of matrices with bounded graver bases and depth parameters and applications to integer programming. Math. Program. , 208(1):497--531, 2024. https://doi.org/10.1007/S10107-023-02048-X doi:10.1007/S10107-023-02048-X

work page doi:10.1007/s10107-023-02048-x 2024
[4]

Closure property of contraction-depth of matroids

Marcin Bria \'n ski, Daniel Kr \' a l', and Ander Lamaison. Closure property of contraction-depth of matroids. Journal of Combinatorial Theory, Series B , 175:240--265, 2025. https://doi.org/10.1016/j.jctb.2025.07.006 doi:10.1016/j.jctb.2025.07.006

work page doi:10.1016/j.jctb.2025.07.006 2025
[5]

u cken, Germany (Virtual Conference) , volume 168 of LIPIcs , pages 26:1--26:19. Schloss Dagstuhl - Leibniz-Zentrum f \

Timothy F. N. Chan, Jacob W. Cooper, Martin Kouteck \' y , Daniel Kr \' a l', and Krist \' y na Pek \' a rkov \' a . Matrices of optimal tree-depth and row-invariant parameterized algorithm for integer programming. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr \" u cken, Germany (Virtual Conf...

work page doi:10.4230/lipics.icalp.2020.26 2020
[6]

Timothy F. N. Chan, Jacob W. Cooper, Martin Kouteck \' y , Daniel Kr \' a l, and Krist \' y na Pek \' a rkov \' a . Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming. SIAM J. Comput. , 51(3):664--700, 2022. https://doi.org/10.1137/20M1353502 doi:10.1137/20M1353502

work page doi:10.1137/20m1353502 2022
[7]

The Monadic Second-Order Logic of Graphs

Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Information and computation , 85(1):12--75, 1990. https://doi.org/10.1016/0890-5401(90)90043-H doi:10.1016/0890-5401(90)90043-H

work page doi:10.1016/0890-5401(90)90043-h 1990
[8]

Branch-depth: Generalizing tree-depth of graphs

Matt DeVos, O - joung Kwon, and Sang - il Oum. Branch-depth: Generalizing tree-depth of graphs. Eur. J. Comb. , 90:103186, 2020. https://doi.org/10.1016/J.EJC.2020.103186 doi:10.1016/J.EJC.2020.103186

work page doi:10.1016/j.ejc.2020.103186 2020
[9]

G. Ding, B. Oporowski, and J. Oxley. On infinite antichains of matroids. Journal of Combinatorial Theory, Series B , 63(1):21--40, 1995. https://doi.org/https://doi.org/10.1006/jctb.1995.1003 doi:https://doi.org/10.1006/jctb.1995.1003

work page doi:10.1006/jctb.1995.1003 1995
[10]

Obstructions and dualities for matroid depth parameters, 2025

Jakub Gajarsk \' y , Krist \' y na Pek \' a rkov \' a , and Michal Pilipczuk. Obstructions and dualities for matroid depth parameters, 2025. http://arxiv.org/abs/2501.09689 arXiv:2501.09689 , https://doi.org/10.48550/ARXIV.2501.09689 doi:10.48550/ARXIV.2501.09689

work page doi:10.48550/arxiv.2501.09689 2025
[11]

Matroid T -connectivity

Jim Geelen, Bert Gerards, and Geoff Whittle. Matroid T -connectivity. SIAM J. Discret. Math. , 20(3):588--596, 2006. https://doi.org/10.1137/050634190 doi:10.1137/050634190

work page doi:10.1137/050634190 2006
[12]

Branch-width, parse trees, and monadic second-order logic for matroids

Petr Hlin e n \' y . Branch-width, parse trees, and monadic second-order logic for matroids. J. Comb. Theory B , 96(3):325--351, 2006. https://doi.org/10.1016/J.JCTB.2005.08.005 doi:10.1016/J.JCTB.2005.08.005

work page doi:10.1016/j.jctb.2005.08.005 2006
[13]

Matroid tree-width

Petr Hlin e n \' y and Geoff Whittle. Matroid tree-width. Eur. J. Comb. , 27(7):1117--1128, 2006. https://doi.org/10.1016/J.EJC.2006.06.005 doi:10.1016/J.EJC.2006.06.005

work page doi:10.1016/j.ejc.2006.06.005 2006
[14]

Addendum to matroid tree-width

Petr Hlin e n \' y and Geoff Whittle. Addendum to matroid tree-width. Eur. J. Comb. , 30(4):1036--1044, 2009. https://doi.org/10.1016/J.EJC.2008.09.028 doi:10.1016/J.EJC.2008.09.028

work page doi:10.1016/j.ejc.2008.09.028 2009
[15]

Finding branch-decompositions and rank-decompositions

Petr Hliněn \' y and Sang - il Oum. Finding branch-decompositions and rank-decompositions. SIAM J. Comput. , 38(3):1012--1032, 2008. https://doi.org/10.1137/070685920 doi:10.1137/070685920

work page doi:10.1137/070685920 2008
[16]

Treedepth and 2-treedepth in graphs with no long induced paths

J e drzej Hodor, Freddie Illingworth, and Tomasz Mazur. Treedepth and 2-treedepth in graphs with no long induced paths. arXiv preprint arXiv:2508.04445 , 2025. https://doi.org/10.48550/arXiv.2508.04445 doi:10.48550/arXiv.2508.04445

work page doi:10.48550/arxiv.2508.04445 2025
[17]

Seweryn, and Paul Wollan

Tony Huynh, Gwena \" e l Joret, Piotr Micek, Michal T. Seweryn, and Paul Wollan. Excluding a ladder. Comb. , 42(3):405--432, 2022. https://doi.org/10.1007/S00493-021-4592-8 doi:10.1007/S00493-021-4592-8

work page doi:10.1007/s00493-021-4592-8 2022
[18]

First order convergence of matroids

František Kardoš, Daniel Kr \' a l', Anita Liebenau, and Luk \' a š Mach. First order convergence of matroids. Eur. J. Comb. , 59:150--168, 2017. https://doi.org/10.1016/J.EJC.2016.08.005 doi:10.1016/J.EJC.2016.08.005

work page doi:10.1016/j.ejc.2016.08.005 2017
[19]

Richard M. Karp. Reducibility among Combinatorial Problems , pages 85--103. Springer US, 1972. https://doi.org/10.1007/978-1-4684-2001-2_9 doi:10.1007/978-1-4684-2001-2_9

work page doi:10.1007/978-1-4684-2001-2_9 1972
[20]

Branch-width of connectivity functions is fixed-parameter tractable, 2026

Tuukka Korhonen and Sang il Oum. Branch-width of connectivity functions is fixed-parameter tractable, 2026. URL: https://arxiv.org/abs/2601.04756, http://arxiv.org/abs/2601.04756 arXiv:2601.04756

work page arXiv 2026
[21]

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Martin Kouteck\' y , Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs . In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) , volume 107 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 85:1--85:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl...

work page doi:10.4230/lipics.icalp.2018.85 2018
[22]

Sparsity - Graphs, Structures, and Algorithms , volume 28 of Algorithms and combinatorics

Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms , volume 28 of Algorithms and combinatorics . Springer, 2012. https://doi.org/10.1007/978-3-642-27875-4 doi:10.1007/978-3-642-27875-4

work page doi:10.1007/978-3-642-27875-4 2012
[23]

Matroid theory

James Oxley. Matroid theory . Oxford University Press, 2011. https://doi.org/10.5555/1197093 doi:10.5555/1197093

work page doi:10.5555/1197093 2011
[24]

Seymour and Robin Thomas

Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. Combinatorica , 14(2):217--241, 1994. https://doi.org/10.1007/BF01215352 doi:10.1007/BF01215352

work page doi:10.1007/bf01215352 1994