Blanc SIMI 2 - Sciences de l'information, de la matière et de l'ingénierie : Sciences de l’information, simulation

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

Submission summary

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).

Project coordinator

Monsieur Jorge RAMIREZ ALFONSIN (CNRS - DELEGATION REGIONALE LANGUEDOC-ROUSSILLON) – jramirez@math.univ-montp2.fr

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

G-SCOP CNRS - DELEGATION REGIONALE RHONE-ALPES SECTEUR ALPES
ECO CNRS - DELEGATION REGIONALE ILE-DE-FRANCE SECTEUR PARIS B
LIRMM CNRS - DELEGATION REGIONALE LANGUEDOC-ROUSSILLON
LIF UNIVERSITE AIX-MARSEILLE II [DE LA MEDITERRANEE]
LRI UNIVERSITE DE PARIS XI [PARIS- SUD]
I3M CNRS - DELEGATION REGIONALE LANGUEDOC-ROUSSILLON

Help of the ANR 344,302 euros
Beginning and duration of the scientific project: - 36 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter