Depth parameters of matroids
Dan Kráľ (Masaryk University)

Width parameters of graphs play a crucial role in algorithmic and structural graph theory, in particular, they are fundamental notions in the theory of graph minors and in fixed parameter complexity. For example, the celebrated theorem of Courcelle asserts that every monadic second order property can be tested in polynomial time when inputs are restricted to classes of graphs of bounded tree-width. Another important graph parameter is tree-depth, which appears in many contexts related to sparsity of graphs.

In this talk, we will survey structural and algorithmic results concerning matroid analogues of tree-width and tree-depth of graphs, particularly focusing on branch-depth and contraction^*-depth. For example, we will present recent structural results demonstrating the closure properties of these two parameters. At the end of the talk, we discuss the relation of the presented concepts to discrete optimization. In particular, we will present matroid based algorithms that uncover a hidden Dantzig-Wolfe-like structure of an input instance (if such structure is present) and transform instances of integer programming to equivalent ones, which are amenable to the existing tools in integer programming.

The most recent results presented in the talk are based on joint work with Marcin Briański, Jacob Cooper, Timothy F. N. Chan, Martin Koutecký, Ander Lamaison, Kristýna Pekárková and Felix Schröder.