Ordonner les ordres

Un treillis sur les ordres partiels

Posted by Viviane on February 7, 2017
Math

Cet article présente de façon simplifiée un travail de recherche récent écrit en collaboration avec Grégory Châtel et Vincent Pilaud.

Ordres partiels

Tout le monde connaît l’ordre naturel des entiers : 1 est plus petit que 2 qui est plus petit que 3, etc. C’est ce qu’on appelle un ordre total. Les ordres partiels sont peut-être un peu moins familiers pour le grand public bien qu’on les retrouve dans de nombreux domaines (par exemple : l’ordre de dépendance des processus sur un ordinateur). Dans cet article, nous cherchons à mettre un ordre sur les ordres.

Tout d’abord, revenons sur la notion d’ordre partiel. Nous passons sur la définition formelle et donnons une idée plus intuitive : un ordre partiel est une façon d’ordonner les éléments d’un ensemble sans que chaque élément soit forcément comparable à tous les autres. Par exemple, si je choisis comme ensemble les couples de nombres $(a,b)$, je peux décider d’un ordre en disant $(a,b) < (c,d)$ si $a$ est plus petit que $c$ et $b$ est plus petit que $d$. Ainsi j’aurais $(2,5) < (3,8)$. Mais selon cette règle, il est impossible de comparer $(2,8)$ et $(3,5)$ : c’est un ordre partiel.

Cela peut sembler un peu abstrait : prenons un exemple de la vie de tous les jours. On peut ordonner les vêtements selon l’ordre dans lequel il faut les enfiler : c’est un ordre partiel. En effet, on doit mettre son t-shirt avant son pull-over, mais l’ordre dans lequel on met ses chaussettes n’est pas important. On pourrait dire alors que le t-shirt est “plus petit” dans l’ordre partiel que le pull-over mais que les chaussettes sont “incomparables” entre elles et incomparables au t-shirt.

Dans cet article, nous allons nous intéresser à la résolution d’une question logique sur un ordre partiel sur les relations binaires. Cette question est issue d’un article de recherche en informatique théorique, et plus précisément, en combinatoire. Vous trouverez ici l’article original The weak order on integer posets.

L’ensemble des relations binaires

Pour énoncer le problème, nous avons besoin de décrire les objets que nous allons ordonner. Jusqu’à présent, nous avons ordonné des nombres, des couples de nombre, et des vêtements. Nous allons maintenant ordonner des graphes sur les entiers. Voici un exemple.

The graph on 1,2,3,4 containing edges: (1, 3), (2, 3), (4, 2), (3,
1)

Nous avons ici un graphe orienté sur les entiers $1,2,3,4$. Pour plus de clarté, on a fait le choix de mettre en bleu et au dessus les arêtes qui vont de la gauche vers la droite (ici, $(1,3)$ et $(2,3)$) et en rouge en dessous celles qui vont de la droite vers la gauche (ici $(4,2)$ et $(3,1)$). On considère l’ensemble de ces graphes sans aucune restriction sur les arêtes.

Pourquoi étudions-nous ces graphes ?

Un autre mot que “graphes” pour décrire ces objets serait relations binaires. L’arête qui relie 1 à 3 signifie que 1 est en relation avec 3. Notez que la relation n’est pas symétrique : 1 est en relation avec 3 mais 3 n’est pas en relation avec 1. La notion de relation binaire est fondamentale en mathématique et en informatique théorique. Les questions que nous abordons ici sont issus de la recherche en combinatoire algébrique et il se trouve que de très nombreux objets de la combinatoire tels que les permutations ou les arbres binaires peuvent être décrits à l’aide de relations binaires.

Combien a-t-on de graphes possibles ?

C’est la première question que se pose un chercheur en combinatoire. Dans ce cas particulier, la réponse est relativement simple. Si on se limite aux graphes sur 1,2,3,4, il y a 3 arêtes possibles partant de 1 : $(1,2)$, $(1,3)$, et $(1,4)$. De même, il y a 3 arêtes possibles partant de 2, ainsi que de 3, ainsi que de 4 (Rappelez-vous que l’arête $(2,1)$ est différente de l’arête $(1,2)$). On a donc en tout $3 \times 4 = 12$ arêtes possibles. Chacune de ces arêtes peut soit être présente, soit absente, ce qui donne $2^{12} = 4096$ graphes possibles ! De façon générale, on a $2^{n(n-1)}$ graphes possibles sur $1,2,\dots,n$.

Un ordre sur les graphes

Nous allons maintenant définir un ordre sur ces graphes, autrement dit : un ordre sur les relations binaires sur les entiers. Plus précisément, on va fixer un nombre $n$ qu’on appellera la taille du graphe, et on va décider d’un ordre partiel sur les $2^{n(n-1)}$ graphes possible sur $1,2,\dots,n$. Notez que le choix de cette définition est relativement arbitraire : elle est motivée par des considérations de recherche en combinatoire algébrique. Nous avons choisi cette définition car elle nous a mené à des questions et des résultats intéressants.

Nous décidons que le plus petit graphe est celui qui contient le maximum d’arêtes bleues (d’un nombre plus petit vers un nombre plus grand) et aucune arête rouge (d’un nombre plus grand vers un nombre plus petit). Symétriquement, le graphe le plus grand est celui qui contient le maximum d’arêtes rouges et aucune arête bleue. Par exemple, pour la taille 4 :

Graphe le plus petit Graphe le plus grand
The graph on 1,2,3,4 containing edges: (1,2),(1,3),(1,4),(2,3),(2,4),(3,4) The graph on 1,2,3,4 containing edges: (4,3),(4,2),(4,1),(3,2),(3,1),(2,1)

On dira qu’un graphe $G$ est plus petit qu’un autre graphe $H$ si $G$ contient au moins les arêtes bleues de $H$ et si $H$ contient au moins les arêtes rouges de $G$ . Autrement dit : pour obtenir un graphe $H$ plus grand que $G$, je peux supprimer des arêtes bleues et rajouter des arêtes rouge. Par exemple :

$G$ $<$ $H$
The graph on 1,2,3,4 containing edges: (1, 3), (2, 3), (4, 2), (3,1)   The graph on 1,2,3,4 containing edges: (1,3),(4,2),(3,1),(4,3),(4,1)

$G$ contient bien l’unique arête bleue de $H$ : $(1,3)$. Et $H$ contient les 2 arêtes rouges de $G$ : $(4,2)$ et $(3,1)$. C’est un ordre partiel car certains graphes ne sont pas comparable, par exemple

$G$ n’est pas comparable à $H$
The graph on 1,2,3,4 containing edges: (1, 3), (2, 3), (4, 2), (3,1)   The graph on 1,2,3,4 containing edges: (1,3),(4,2),(2,1)

En effet, $G$ contient bien l’unique arête bleue de $H$, mais $H$ ne contient pas l’arête $(3,1)$ rouge de $G$. Voici par exemple une représentation de l’ordre partiel sur les 4 graphes de taille 2.

Ordre partiel sur les graphes de taille 2

En taille 3, on a déjà 64 graphes et on obtient :

Ordre partiel sur les graphes de taille 3

Des graphes qui sont des ordres

On a donc définit un ordre sur les graphes. À présent, nous allons voir que certains de ces graphes peuvent eux mêmes être considérés comme des ordres partiels ! Observez le graphe suivant.

The graph on 1,2,3,4,5,6 containing edges: (1,3),(2,3),(1,4),(5,6),(4,3),(6,3), (5,3)

On dira qu’un nombre $a$ est plus petit dans le graphe qu’un nombre $b$ s’il existe une arête de $a$ vers $b$. On a par exemple que 1 est plus petit dans le graphe que 3 et 4, et que 5 est plus petit dans le graphe que 3. Certains nombres ne sont pas comparables car ils ne sont pas reliés par une arête : 1 et 2, 5 et 4, 1 et 5, etc. Le graphe définit donc un ordre partiel sur les nombre $1,2,3,4,5,6$. Notez qu’il y a donc 2 ordres distincts définis sur ces entiers : l’ordre naturel des nombre et l’ordre du graphe !

Tous les graphes définissent-ils un ordre partiel ? Voyons l’exemple suivant.

The graph on 1,2,3,4 containing edges: (1, 3), (2, 3), (4, 2), (3,1)

Ici, on aurait que 1 est plus petit dans le graphe que 3, lui même plus petit que 1. On dit que la relation n’est pas antisymétrique. Par ailleurs, 4 est plus petit que 2, qui lui est plus petit que 3. Mais il n’y a pas d’arête directe entre 4 et 3, donc 4 n’est pas plus petit dans le graphe que 3. On dit que la relation n’est pas transitive. Rappelons-nous l’ordre naturel des entiers et l’ordre des vêtements, on pourra vérifier qu’ils sont bien antisymétriques et transitifs. En fait, pour être une relation d’ordre, une relation doit être à la fois antisymétrique et transitive : on va sélectionner les graphes qui vérifient ces propriétés.

non antisymétrique antisymétrique antisymétrique
non transitif non transitif transitif
The graph on 1,2,3,4 containing edges: (1, 3), (2, 3), (4, 2), (3,1) The graph on 1,2,3,4 containing edges: (1,3),(4,2),(2,1) The graph on 1,2,3,4,5,6 containing edges: (1,3),(4,2),(2,1),(2,3), (4,1), (4,3)

Des 64 graphes sur $1,2,3$, seulement 19 sont des relations d’ordres. On les ordonne entre elles en utilisant l’ordre sur les graphes et on obtient ce qu’on appelle l’ordre induit sur les relations d’ordre.

Ordre partiel sur les relations d'ordre

À quoi correspond cet ordre ? Que signifie-t-il ? On remarque la chose suivante : les relations bleues sont celles qui sont les mêmes que dans l’ordre naturel des entiers tandis que les relations rouges sont celles qui sont inversées. Ainsi le plus petit graphe est celui pour lequel 1 est plus petit que 2 qui est plus petit que 3 : c’est l’ordre naturel entre 1, 2 et 3. Dans le plus grand graphe, on a 3 plus petit que 2, plus petit que 1, soit le contraire de l’ordre classique. En clair, plus un graphe est petit dans notre ordre, plus il est proche de l’ordre naturel et plus il est grand, plus il est proche de l’ordre inverse !

Inf et Sup

Pour terminer, nous allons réfléchir à certaines propriétés de notre ordre. Si j’ai deux graphes $G$ et $H$, puis-je trouver un graphe $I$ qui soit le plus grand élément possible plus petit que $G$ et $H$ (un infimum) ? De même, existe-t-il un graphe $S$ qui soit le plus petit élément plus grand que $G$ et $H$ (un supremum) ? C’est une question très courante en théorie des ordres partiels, un ordre partiel qui vérifie cette propriété s’appelle un treillis.

Si on se contente de regarder tous les graphes sans les contraintes d’antisymétrie et de transitivité, il est facile de répondre oui à cette question. En effet, un graphe qui est plus petit que $G$ et $H$ doit contenir toutes les arêtes bleues qui sont soit dans $G$, soit dans $H$, il doit donc contenir l’union des arêtes bleues. Par ailleurs, toutes ses arêtes rouges doivent être contenues à la fois dans $G$ et dans $H$, elles doivent donc appartenir l’intersection des arêtes rouges. Ainsi, l’infimum sera le graphe obtenu par l’union des arêtes bleues et l’intersection des arêtes rouges. Symétriquement, le supremum sera obtenu par intersection des arêtes bleues et l’union des arêtes rouges. Voilà par exemple deux graphes avec leur infimum (en dessous) et supremum (au dessus).

Graphe G (1, 3), (2, 3), (4, 2), (3,
1), Graphe H (1, 3), (1, 4), (3, 2), (3,
1), infimum (1, 3), (2, 3), (1, 4), (3,
1), supremum (1, 3), (4, 2), (3, 2), (3,
1)

Mais que se passe-t-il si on rajoute les contraintes d’antisymétrie et de transitivité ? Avec seulement l’antisymétrie, il est encore assez simple de répondre. Observez par exemples les deux graphes antisymétriques ci-dessous avec leur infimum et supremum calculés comme nous l’avons expliqué : aussi bien l’infimum que le supremum sont eux aussi antisymétriques.

Graphe G (1, 3), (4, 2), (2, 1), Graphe H (1, 3), (2, 4), (2, 1), (4,
3), infimum (1, 3), (2, 4), (2, 1), supremum (1, 3), (4, 2), (2, 1), (4,
3)

On peut prouver ce résultat de façon générale pour tout couple de graphes antisymétriques et nous invitons le lecteur à tenter cette petite démonstration ! On dit que l’ensemble des graphes antisymétriques forme un sous-treillis du treillis des graphes. Les choses se compliquent pour les relations transitives. Regardez l’exemple qui suit : les deux graphes de départ sont bien transitifs mais l’infimum et le supremum ne le sont pas.

Graphe G (1,2),(1,3),(3,2),(4,2),(4,1),(4,3), Graphe H 1,3),(2,4),(2,3),(4,3),(2,1),(4,1), infimum 1, 2), (1, 3), (2, 3), (2,
4), (4, 3), (4, 1), supremum (1,3),(3,2),(4,2),(4,1),(4,3),(2,1)

On peut tout de même prouver que l’ordre induit sur les relations d’ordre est aussi un treillis : il faut partir des infimum et supremum calculés comme ci-dessus et ajouter / supprimer les arêtes nécessaires. Nous laissons le lecteur sur ce problème et l’invitons à chercher la solution. Partez du treillis des 19 relations d’ordres que nous avons dessiné pour la taille 3 : arrivez-vous à trouver sur le dessin les infimum / supremum de deux graphes pris “au hasard” ? À partir de vos observations, pouvez-vous donner une méthode de calcul générique qui vous donne le résultat ? La réponse et la démonstration associée se trouvent dans l’article The weak order on integer posets avec de nombreux autres résultats que nous n’avons pas évoqué ici.