Une de ces directions est celle des matroïdes. L'hypergraphe où " l'algorithme glouton " trouve toujours l'optimum du problème, est exactement celle des (delta-)matroïdes. Bien que l'algorithme glouton est très particulier, le problème de " l'intersection de deux matroïdes " contient déjà la théorie des flots dans les réseaux. Les matroïdes orientés formalisent les propriétés de convexité : de nombreux résultats et problèmes de la combinatoire géométrique peuvent être formulés à ce niveau plus abstrait.
Une autre grande direction de l'optimisation combinatoire est la théorie des couplages non-bipartis et ses généralisations.
Un des grands problèmes de l'optimisation combinatoire moderne est de trouver un " chapeau commun " (généralisation commune) à ces deux directions et aussi des généralisations communes à leurs résultats.
Une structure, plus générale que celle des matroïdes, a été récemment introduite par A. Bouchet et W. Cunningham : les systèmes de sauts. Une structure qui selon les résultats les plus récents pourrait devenir ce " chapeau commun " des deux grandes directions de l'optimisation combinatoire, citées ci-dessus.
Les matroïdes généralisent l'algèbre linéaire et les graphes. Les matroïdes orientés saisissent la convexité (la programmation linéaire) et les graphes orientés. W. Bienia et M. Sadli ont travaillé sur des problèmes ouverts concernant les matroïdes orientés, en continuant le travail précédent de W. Bienia.
Dans [15] et [22], B. Novick et A. Sebö établissent des connexions entre les propriétés combinatoires des espaces affines binaires et des propriétés de matroïdes sous-jacents. Ces résultats ont été utilisés plus tard dans l'étude des programmes linéaires " binaires " en nombres entiers.
Dans [24] et [25] plusieurs conjectures concernant les systèmes de sauts ont été démontrées.
Ces démonstrations utilisent la " boîte à outils " développée par L. Lovász au cours d'une rencontre que nous avons organisée à Grenoble, en juin 1995. Le thème de cette rencontre informelle était les systèmes de sauts. Elle a permis de réunir des spécialistes mondiaux de l'optimisation combinatoire : L. Lovász, A. Bouchet, M. Conforti, G. Cornuejols, W. Cunningham, A. Frank, M. Lomonosov, etc., et elle a donné lieu à des articles, dont celui de L. Lovász (Journal of Combinatorial Theory, avril 1997), devenus déjà des standards. D'autres sont à venir (dont la forme écrite de [24] et [25] et un article de Cunningham, Geelen et Sebö). On peut dire que cette rencontre a posé les fondements d'un sujet qui venait de naître.
M. Sadli et A. Sebö travaillent sur l'application des systèmes de sauts à des problèmes de multiflots, initiée par [9].
L'étude de structures critiques peut donner un cadre efficace
pour développer des algorithmes de structure et démontrer
des théorèmes minimax.
Dans [7], les hypergraphes minimaux par rapport à la propriété
qu'un algorithme " naturel et glouton " ne trouve pas un nombre maximum
d'hyper-arêtes disjointes, sont caractérisés. L'algorithme
de reconnaissance de ces hypergraphes est basé sur cette structure.
Dans [16, 23] les structures minimales où l'optimum d'un programme
linéaire en nombres entiers ne peut pas être déterminé
par la programmation linéaire, sont étudiés. C'est
un cas spécial du théorème de Lehman, qui contient
des problèmes combinatoires importants, comme le packing de cycles
dans des graphes représentés sur des surfaces non-orientées.
Une étude similaire est en cours par les membres de l'équipe
pour les ensembles de vecteurs " minimaux non systèmes de sauts
", et la structure des trous dans ces systèmes.
Les graphes imparfaits minimaux donnent un exemple déjà classique du même type d'étude. La recherche grenobloise dans ce domaine, commune avec l'équipe Graphe du département, est liée avec des résultats pionniers de l 'école arménienne et grenobloise. L'article [10] écrit à Grenoble, donne la démonstration " du Grand Livre " (terme de Paul Erdös qui imagine que les " vraies " preuves, les plus simples, sont déjà écrites dans un Grand Livre, et certains d'entre nous ont la chance d'en " lire " quelques uns) de la structure de base des graphes imparfait-minimaux. Un article de F. Maffray et M. Preissmann avec des visiteurs à Grenoble, et [17, 18] établissent des nouvelles propriétés des graphes imparfait-minimaux, et démontrent que les seules candidats jusqu'à présent à pouvoir contenir des contre-exemples à la conjecture des graphes parfaits n'en contiennent point. Cette question a été initiée et motivée par le séminaire informel SIROCO du département de Mathématiques discrètes.
Les T-joins généralisent les couplages, les chemins, ou les tours de postier (chinois) dans les graphes, et contiennent aussi le " modèle de Pinter " concernant la conception des circuits intégrés. Les T-coupes généralisent le problème des multiflots planaires.
Au début des années 90, une méthode qui consiste à étudier la structure des distances pondérées dans les graphes a été développée par notre équipe. L'article [19] résume ces résultats et va au bout de ces méthodes, qui a des conséquences en physique, dans la conception de circuits intégrés (à travers les multiflots) et aux coupes des graphes planaires.
M. Burlet [5], avec le professeur russe A. Karzanov ont défini
une extension de cette notion, les (T,d)-joins, et sont arrivés
à une généralisation considérable des méthodes
de combinatoire polyédrale sous-jacents, et des résultats.
Une conjecture de A. Sebö caractérisant les graphes de Seymour
vient d'être démontrée par un post-doc de notre équipe
et des collègues russes [11,8].