page d'accueil   sommaire  

Géométrie de polytopes d'ordres [Geometry of order polytopes]

A chaque famille de relations sur un ensemble fini est associé le polytope qui est l'enveloppe convexe des vecteurs caractéristiques de ces relations. La géométrie des polytopes convexes ainsi obtenus est étudiée, notamment en vue de déterminer des facettes. Les cas les plus importants sont ceux des ordres totaux, des préordres totaux, des ordres partiels; ils apparaissent également en optimisation combinatoire. [To each family of relations on a finite set, one associates a polytope which is the convex hull of all the characteristic vectors of those relations. The geometry of the resulting convex polytopes is investigated, with the particular aim of producing facets. The proeminent cases are those of linear orders, weak orders, partial orders; the associated polytopes also appear in combinatorial optimization.]



responsables


Jean-Paul DOIGNON Samuel FIORINI


disciplines et mots clés déclarés


Géométrie

polytope convexe relation d'ordre