Catálogo de publicaciones - libros

Ce premier chapitre présente les notions de base de la théorie des ensembles ordonnés finis et donne une idée de la variété des domaines où on les rencontre. Il n’est pas destiné à une lecture suivie, mais à servir de texte de référence pour la définition et l’illustration de notions utilisées dans les autres chapitres. En particulier, il ne contient pas les démonstrations des quelques résultats qui y sont énoncés (on trouvera ces démonstrations dans d’autres chapitres et/ou dans des exercices). Dans la première section nous donnons les concepts et le vocabulaire permettant de définir, représenter et décrire un ensemble ordonné, et nous introduisons plusieurs graphes – de comparabilité, d’incomparabilité, de couverture et de voisinage – qui lui sont naturellement associés. La seconde section présente des ensembles ordonnés apparus dans divers champs disciplinaires, des mathématiques elles-mêmes aux sciences sociales en passant par la biologie et l’informatique. Nous définissons les notions de sous-ensemble ordonné, de chaîne, d’antichaîne et d’extension d’un ensemble ordonné dans la section 1.3 et les notions de supremum, d’infimum, d’éléments irréductibles et de parties commençantes ou finissantes dans la section 1.4. La section 1.5 décrit des procédés fondamentaux de construction (substitution, produit direct, etc.) qui, à deux ou plusieurs ensembles ordonnés, en associent un nouveau.

Ce livre contient des résultats, comme les théorèmes de Dilworth (au chapitre 4) ou d’Hiraguchi (au chapitre 6), valables pour tout ensemble ordonné. Toutefois ce type de résultat est assez rare. La notion d’ordre, bien que fort restrictive relativement à celle de relation quelconque, reste en effet très générale comme en témoigne l’immensité du nombre d’ordres différents que l’on peut obtenir sur un ensemble de cardinal peu élevé (plus de deux millions de types d’ordres sur un ensemble à 10 éléments ! Voir l’annexe C). Mais, en pratique, les ordres apparaissant dans la « nature » appartiennent le plus souvent à une classe particulière d’ordres. Ces classes peuvent être définies de très nombreuses manières. Elles s’obtiennent, par exemple, en fixant la valeur d’un paramètre (comme les ordres de dimension 2 étudiés à la section 6.3), en interdisant la présence de certaines configurations (comme les ordres d’intervalles de l’exemple 1.22 et de la section 2.2), en construisant la classe par itération de certaines opérations sur une famille d’ordres initiaux (les ordres séries-parallèles définis à la section 2.2). Nous donnons ci-dessous quelques-unes des classes d’ordres les plus courantes et que l’on retrouvera constamment dans cet ouvrage. Bien que nous ne les définissions ici que d’une seule manière, on verra dans les exercices ou ultérieurement que ces classes ont souvent plusieurs définitions alternatives, ce qui explique qu’elles aient pu apparaître indépendamment dans des contextes variés et renforce leur intérêt.

Soit P un ensemble ordonné modélisant, par exemple, un problème d’ordonnancement (cf. la section 7.5 du chapitre 7). Le calcul de caractéristiques de l’ensemble ordonné lié au problème, par exemple celui d’extensions linéaires de P , nécessite l’implémentation d’un algorithme où P sera représenté par une structure appropriée de données. En particulier, on peut utiliser une représentation des éléments de P par des suites composées de r symboles 0 et 1. Il faut pour ceci que, si (et seulement si) x et y sont deux éléments de P vérifiant x < y et que c ( x ) et c ( y ) sont les r -suites représentant ces éléments, on ait c ( x ) < c ( y ), où < est l’ordre du produit direct 2 r . L’application c de P dans ce produit direct doit donc conserver l’ordre de P . On a ainsi un exemple parmi bien d’autres où l’on est amené à considérer les applications d’un premier ensemble ordonné dans un second, conservant ou inversant l’ordre du premier. Ce chapitre est consacré à l’étude de telles applications, appelées morphismes 1. On en définit différents types fondamentaux, comme les codages (ou plongements ), les fermetures et les ouvertures , les applications résiduelles , résiduées et galoisiennes . On s’intéresse aux liens entre ces divers types d’applications, à des exemples canoniques, ainsi qu’à des développements naturels.

Les problèmes de tri, de recherche et d’ordonnancement que l’on rencontre, par exemple, en informatique et en recherche opérationnelle, sont fréquemment liés à la détermination du cardinal maximum d’une antichaîne d’un ensemble ordonné, c’est-à-dire de sa largeur. Nous donnons plus loin deux illustrations de cette observation générale (exemple 4.28 et exercice 4.2). Ce chapitre est donc dédié à l’étude de cette largeur et à des questions connexes. Tout d’abord, le théorème de Dilworth établit que, pour tout ensemble ordonné P , le cardinal minimum d’une partition de P en chaînes est égal à la largeur de P . C’est l’un des résultats les plus célèbres de la combinatoire, et les deux premières sections de ce chapitre lui sont consacrées. Ce théorème est énoncé et démontré dans la section 4.1, où est aussi décrit son proche environnement. La section 4.2 porte sur ses conséquences dans le cas particulier des ensembles ordonnés bipartis, et notamment sur son équivalence avec le théorème de Künig–Egerváry portant sur les couplages et les transversales dans une telle structure. Dans les notes de ce chapitre, on fait ressortir l’importance de cette équivalence, qui conduit à la détermination effective de la largeur par des algorithmes de flots issus de la théorie des graphes. On y rappelle que le théorème de Dilworth équivaut aussi à trois autres résultats fondamentaux de la combinatoire : le théorème de Künig–Hall et les théorèmes de Menger et de Ford et Fulkerson. Ceux-ci sont tout à fait essentiels et ont de nombreuses applications, par exemple, aux matrices binaires et aux problèmes d’affectation pour le premier sous sa forme la plus connue (exercice 4.6), et aux réseaux de transport pour les deux autres.

Les ensembles ordonnés appelés treillis ont été définis au chapitre 1 et, au chapitre 2, on a introduit des classes particulières de treillis tels les treillis distributifs, modulaires ou semi-modulaires. La classe des treillis distributifs est la plus importante pour plusieurs raisons. D’abord, on peut noter que les treillis distributifs, du fait justement de la distributivité entre leurs deux opérations, sont ceux dont le maniement algébrique est le plus aisé. Ensuite, bon nombre d’ordres intervenant naturellement en mathématiques pures ou appliquées s’avèrent des treillis distributifs. On a déjà cité le cas des ensembles totalement ordonnés ainsi que celui de l’ensemble des parties d’un ensemble muni de l’ordre d’inclusion, structure isomorphe à celle d’un produit direct de chaînes à deux éléments. Une généralisation de ce cas est le treillis distributif obtenu en faisant le produit direct de chaînes de longueur quelconque. Ainsi, lorsque dans la modélisation d’un problème de décision, on considère que les choix possibles sont évalués selon plusieurs ordres totaux correspondant à différents critères, ces choix correspondent à des éléments du treillis distributif produit de ces ordres. Enfin et surtout, il existe une correspondance fondamentale entre ensembles ordonnés et treillis distributifs, qui fait que toute propriété ou problème sur les ensembles ordonnés peut se « traduire »en une propriété ou un problème sur les treillis distributifs (et inversement). Par exemple, dans les problèmes d’ordonnancement où l’on doit rechercher une extension linéaire d’un ensemble ordonné, le passage au problème correspondant sur le treillis distributif associé se révèle fructueux (cf. la section 7.5).

Nous avons déjà eu plusieurs fois l’occasion de considérer des codages (définition 3.1) d’un ensemble ordonné dans un autre ensemble ordonné. Il est en effet naturel, devant un ensemble ordonné pouvant avoir une structure complexe, de chercher à le représenter dans une structure ordinale plus simple. Dans ce chapitre, nous prendrons comme structure simple les ensembles ordonnés obtenus comme produits directs de chaînes (cf. la section 1.5.2). Un codage de l’ensemble ordonné P sera donc une application envoyant P dans un sous-ensemble ordonné, isomorphe à P , d’un tel produit. Cette notion se particularise lorsqu’on impose des conditions sur la cardinalité des chaînes. Ainsi, quand toutes les chaînes sont de cardinalité k ( k étant un entier fixé), comme nous le supposerons dans la suite, nous parlerons de k-codage . Le nombre minimum de chaînes nécessaires pour qu’il existe un k -codage de P s’appellera la k-dimension de P .

Au chapitre 1 (exemple 1.21), on a mentionné que la classique fonction d’utilité u des économistes qui représente les préférences d’un agent sur un ensemble de biens (le bien x est préféré au bien y si u ( x ) > u ( y )) définit un ordre (strict) particulier, dit ordre fort, sur cet ensemble. Dans cette modélisation des préférences par une fonction d’utilité, deux biens de même utilité sont considérés comme indifférents. La relation d’indifférence de l’agent est donc transitive. Or, on a constaté depuis longtemps que cette hypothèse n’est pas nécessairement vérifiée et l’on a défini d’autres modèles ordinaux pour la préférence qui, tout en permettant une représentation numérique d’icelle, permettent aussi d’avoir une relation d’indifférence non transitive. Ce sont ces modèles et leurs représentations numériques que nous allons développer dans cette section. Plusieurs points sont d’abord à mentionner ou préciser.