Nouvelles Tendances dans les Matroides : Polytopes des bases, Structures, Algorithmes et Interactions – TEOMATRO

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 simpliciales, ensembles des indépendants, treillis des fermés, une 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, introduit 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ée 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 pseudodroites, aux noeuds et fonctions sous-modulaires.