Navigation – Plan du site

Le cône des représentations d’un ordre d’intervalles

The representation cone of an interval order
Jean-Paul Doignon et Christophe Pauwels
p. 55-71

Résumés

Un ordre d’intervalles est donné sur un ensemble fini d’éléments. Définies de manière appropriée, ses représentations numériques forment un polyèdre convexe. Nos résultats décrivent la structure géométrique de ce polyèdre. Les facettes correspondent à des objets de quatre types : les éléments minimaux, les éléments contractibles ainsi que les nez et les creux de l’ordre d’intervalles (ces deux dernières notions sont inspirées de Doignon et Falmagne [1997]). Le polyèdre n’a qu’un seul sommet, qui est la représentation minimale de l’ordre d’intervalles (au sens de Doignon [1988a] ; plusieurs nouvelles propriétés sont établies ici). Les représentations forment donc un cône convexe. Nous caractérisons les rayons extrêmes de ce cône. L’unicité du sommet est un résultat surprenant, car Balof, Doignon et Fiorini [2012] ont obtenu, pour le polyèdre des représentations d’un semiordre, de nombreux exemples à sommets multiples

The representation cone of an interval order

A fixed, interval order is considered on a finite set of elements. When appropriately defined, its representations form a convex polyhedron. Our results describe the geometricstructure of the polyhedron. The facets are in a one-to-one correspondence with the objects of oneof four types: the minimal elements, the contractible elements as well as the noses and the hollowsof the interval order (the latter notions are inferred from Doignon and Falmagne [1997]). Thepolyhedron has only one vertex, which is the minimal representation (in the meaning of Doignon[1988a]; new properties are established here). All representations thus form a convex cone. Wecharacterize the extreme rays of this cone. The uniqueness of the vertex came as a surprise tous surprise because Balof, Doignon and Fiorini [2012] obtained, for the polyhedron formed by allrepresentations of a semiorder, numerous examples with multiple vertices.

Haut de page

Pour citer cet article

Référence électronique

Jean-Paul Doignon et Christophe Pauwels, « Le cône des représentations d’un ordre d’intervalles », Mathématiques et sciences humaines [En ligne], 195 | Automne 2011, mis en ligne le 09 janvier 2012, consulté le 18 décembre 2017. URL : http://journals.openedition.org/msh/12061

Haut de page

Auteurs

Jean-Paul Doignon

Université Libre de Bruxelles, Département de mathématique, C.P. 216, Boulevard du Triomphe, 1050 Brussels, Belgium, doignon@ulb.ac.be

Articles du même auteur

Christophe Pauwels

pauwelsch@gmail.com

Haut de page

Droits d’auteur

© École des hautes études en sciences sociales

Haut de page