Cliquez pour agrandir.
L'objet de cette thèse est de définir et d'étudier, de façon intrinsèque et de façon constructive, une application naturelle qui à un matroïde orienté ordonné associe une de ses bases. Pour un matroïde orienté ordonné donné, elle induit une correspondance, déterminée par certaines conditions, entre l'ensemble de ses réorientations et celui de ses bases.
Une condition fondamentale à satisfaire est que les activités soient conservées. Les activités d'une base dans un matroïde ordonné, définies par Tutte, sont deux paramètres entiers duaux, de même que les activités d'un matroïde orienté ordonné, définies par Las Vergnas. En très bref, elles situent ces objets par rapport aux bases minimales et maximales pour l'ordre lexicographique. La correspondance est appelée ainsi correspondance active canonique du matroïde orienté ordonné, et constitue une preuve bijective de propriétés énumératives connues du polynôme de Tutte.
Une autre condition est qu'elle soit invariante par passage au dual : la dualité est utilisée partout ici de façon essentielle, dans les caractéristiques fondamentales comme dans les algorithmes.
La correspondance active canonique a des propriétés géométriques remarquables, et peut-être construite inductivement soit en utilisant les mineurs relativement au plus grand élément, soit en utilisant une décomposition des activités qui réduit le problème aux activités (1,0). En termes de bases, cette décomposition donne une nouvelle expression du polynôme de Tutte utilisant les invariants béta de certains mineurs. En termes de réorientations, cette décomposition conduit à une notion de classes d'activités de réorientations, lesquelles sont en bijection active avec les bases. En outre, cette bijection peut-être raffinée en une bijection active entre tous les sous-ensembles d'éléments, qui induit une bijection active entre les régions du matroïde orienté et les parties sans circuit brisé (circuit moins son plus petit élément) du matroïde (faces du complexe NBC).
Dans le cas d'un graphe, on obtient notamment une bijection active entre les arbres couvrants internes (ceux dont les éléments du complémentaires ne sont jamais le plus petit de leur cycle fondamental par rapport à l'arbre) et les orientations acycliques ayant un unique puits fixé ; ainsi qu'une bijection entre arbres couvrants d'activités (1,0) (ceux qui, en plus, sont le plus loin possible de la base minimale) et les orientations acycliques ayant un unique puits et une unique source adjacents fixés.
Dans le cas d'un arrangement d'hyperplans, on obtient notamment une bijection active entre les simplexes internes et les classes d'activités de régions, ainsi qu'une bijection entre les simplexes d'activités (1,0) et les régions bornées. Si les hyperplans sont en position générale, cette dernière bijection s'obtient en appliquant le même programme linéaire simultanément à toutes les régions bornées, de chaque côté d'un hyperplan distingué, noyau de la forme linéaire à optimiser.
L'application générale revient ainsi à une extension de la version combinatoire dans les matroïdes orientés de la programmation linéaire : d'une part chaque réorientation se décompose en régions bornées dans des mineurs du matroïde orienté et de son dual, et d'autre part pour chaque région bornée, au lieu d'un sommet pour une fonction objective, on optimise une suite de faces emboîtées pour une suite de fonctions objectives.
Cette application apparait naturellement dès que l'on considère un ordre total sur les éléments des matroïdes orientés. Elle décrit, intuitivement, un phénomène d'attraction dirigée par l'ordre des éléments, et peut-être appelée application (attr)active des matroïdes orientés ordonnés.