UVictoria Discrete Math Seminar: Dan Kráľ

Depth and width parameters of graphs, e.g., tree-width, path-width and tree-depth, play a crucial role in algorithmic and structural graph theory. These notions are of fundamental importance in the theory of graph minors, fixed parameter complexity and combinatorial sparsity.

In this talk, we will survey structural and algorithmic results concerning width and depth parameters of matroids. We will view matroids as purely combinatorial objects and discuss their structural properties related to depth and width decompositions. As an algorithmic application, we will present matroid based algorithms that can uncover a hidden Dantzig-Wolfe-like structure of instances of integer programs (if such structure is present).

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.