New trends in Matroids : Base Polytopes, Structure, Algorithms and Interactions – TEOMATRO

Matroid theory is a subject that unify several areas and that helps to explain and discover the common properties of such areas. Studying problems in this more general setting often gives new insight to different problems and their connections

A matroid can be basically seen as a structure that captures the notion
of the linear dependency in vector spaces.
The theory of matroid can be approached from many different points of view. A matroid can be defined as a simplicial complex of independent sets, a lattice flats, a closure relation, and in many other different ways.
A relatively new point of view is the study of matroid polytopes, which in some sense, are the natural combinatorial setting of matroids in algebraic geometry and optimisation.
The study of the decomposition of a matroid polytope into smaller matroid polytopes, introduced by L. Lafforgue (Fields medal 2002), has recently received significant attention. Indeed, such decomposition notion turns out to be a powerful tool and it has been used in many different contexts.
For instance, they are treated in relation with hyperplane arrangements questions and applied while investigating tropical vector spaces. Moreover, it is shown in that important matroid functions (as Tutte polynomial) are well-behaved under matroid polytope decomposition.

A better conceptual and mathematical understanding of matroid polytopes is required since this would have importants algorithmic and theoretical consequences. The goal of this project is to develop the study of matroid polytopes and its interactions with other subjects. The project is divided into two related parts. Firstly, we shall study combinatorial properties of the base matroid graphs (that is, the graphs associated to the 1-skeleton of matroid polytopes). We will also investigate conditions for the existence (or nonexistence) of matroid polytope decompositions (as discussed above) and the major cut set expansion matroid problem.

Secondly, we will explore (apply our findings) several important algorithmic and theoretical problems related to matroids. We shall devote special attention to Ehrhart and Tutte polynomials (and polytope volume computations), triangulations (coverings, Hilbert bases), double pseudolines arrangements, knots and submodular functions (polymatroids, Potts model, edge-connectivity augmentation of (hyper)graphs).