Aim of the project

Various graph characterization and optimization problems can be treated conveniently by applying the basic tools of matroid theory. Besides revealing the true background of known results, matroids are often unavoidable in solving natural optimization problems in which matroids do not appear explicitly at all. We propose to study several, seemingly unrelated questions that stem from the same root: understanding the structure of bases or independent sets of certain matroids, or more generally, of discrete convex and concave functions. The goal of the project is threefold.

  • First, we would like to provide a deeper understanding of the structure of base-families of matroids while focusing on the conjectures of Gabow on cyclic orderings of matroids and of White on compatible basis sequences.
  • Second, with the help of the more thorough understanding of the underlying matroid structure, we would like to attack long-standing graph and matroid optimization problems, with particular interest in Woodall’s conjecture on the maximum number of pairwise disjoint dijoins and Rota’s conjecture on the existence of transversal bases.
  • Finally, we consider interdisciplinary problems that arise naturally in applications such as inverse and bilevel optimization and dynamic pricing schemes for combinatorial markets.