La théorie des matroïdes est un sujet qui regroupe plusieurs domaines de recherche et qui permet d'expliquer et de découvrir des propriétés communes à ces domaines. L'étude de problèmes dans ce cadre plus général donne des nouveaux points de vue aux différents problèmes.

La structure des matroïdes est une version combinatoire de la dépendance linéaire dans les espaces vectoriels où n'interviennent plus que deux valeurs zéro et non zéro. La théorie des matroïdes peut être abordée de différentes manières : complexes simpliciaux, ensembles des indépendants, treillis des fermés, relation de fermeture et de nombreuses autres façons. Un récent point de vue consiste à étudier les polytopes des matroïdes, qui se situent dans des cadres combinatoires naturels des matroïdes en géométrie algébrique et en optimisation. L'étude de la décomposition d'un polytope de matroïdes en polytopes des matroïdes plus petits, introduite par L. Lafforgue (médaille Fields 2002), a récemment reçu beaucoup d'attention. En effet, une telle notion de décomposition se révèle être un outil puissant et a été utilisée dans divers contextes. Citons à titre d'exemples, l'utilisation de cette notion dans le cadre d'arrangements d'hyperplans, son application à des travaux de recherche sur les espaces vectoriels tropicaux. En outre, il a été démontré que d'importantes fonctions de matroïdes (comme le polynôme de Tutte) sont simplifiées lors de décompositions de polytopes des matroïdes. Cependant, une meilleure compréhension conceptuelle et mathématique du polytope des matroïdes est nécessaire en raison de ses très importantes conséquences théoriques et algorithmiques.

L'objectif de notre projet est de développer l'étude du polytope des matroïdes et de ses interactions avec d'autres sujets. Le projet est divisé en deux parties. Premièrement, on cherchera des propriétés combinatoires du graphe des bases des matroïdes (c'est-à-dire, les 1-skeleton associés aux polytopes des matroïdes). On étudiera également les décompositions des polytopes des matroïdes ainsi que le problème majeur appelé cut set expansion. Deuxièmement, on explorera plusieurs problèmes théoriques et algorithmiques importants liés aux matroïdes. On portera attention aux polynômes de Tutte et de Ehrhart, aux triangulations, aux arrangements de double pseudodroites, aux noeuds et fonctions sous-modulaires.

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 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 pseudoline arrangements, knots and submodular functions (polymatroids, Potts model, edge-connectivity augmentation of (hyper)graphs).