Obstructions for bounded branch-depth in matroids

Width paramaters and associated decompositions of combinatorial structures play a prominent role both in combinatorics and algorithm design. The most studied notion is that of tree-width for graphs and the associated notion of tree-decompositions; vaguely speaking, a graph has small tree-width if it can be split along small vertex cuts into simple pieces in a tree-like fashion. The notion of tree-decompositions turned out to be of key importance in the Graph Minor Project of Robertson and Seymour. The most prominent result concerning tree-width of graphs is Courcelle’s Theorem, which asserts that every graph property expressible in the monadic second-order logic can be decided in linear time for any class of graphs with bounded tree-width. Other widely used graph width parameters include clique-width, which splits a graph in a tree-like fashion along separations with a small complexity and which is bounded in both direction by rank-width, and tree-depth, which measures how local a graph is (and so prevents the existence of long paths).

Analogous results exist for matroids, a combinatorial structure that abstracts the notion of linear independance and so generalizes graphs in a certain sense. In this setting, branch-decompositions play a similarly important role. There are two extensions of tree-depth to matroids, both named branch-depth. One of the extensions is inspired by rank-width and rank-depth of graphs, and the other by tree-width. The paper addresses an important problem concerning a structural characterization of the former notion.

DeVos, Kwon and Oum [European J. Combin. 90 (2020)] conjectured that every matroid with large branch-depth contains the cycle matroid of a large fan graph or a large uniform matroid as a minor; analogous results for graph width parameters, in particular, graph tree-width and tree-depth, have many applications in structural graph theory. The main result of the paper asserts that every matroid with large branch-depth contains the cycle matroid of a large fan graph as a minor unless it has large branch-width, which verifies the conjecture of DeVos et al. for all matroids representable over a fixed finite field.