Ordre de domination

En mathématiques discrètes, l’ordre de domination (en anglais dominance order, appelé aussi dominance ordering, majorization order, natural ordering) est un ordre partiel sur l'ensemble des partitions d'un entier naturel qui joue un rôle important en combinatoire algébrique et en théorie des représentations, spécialement dans le contexte des fonctions symétriques et des représentations du groupe symétrique.

Ordre de domination sur les partitions de l'entier 6. Les sommets du graphe sont les partitions ; un arc indique que la partition supérieure domine la partition inférieure.

Définition

Soient $p=(p_{1},p_{2},\ldots )$ et $q=(q_{1},q_{2},\ldots )$ deux partitions d'un entier $n$, avec $p_{1}\geq p_{2}\geq \cdots$ et $q_{1}\geq q_{2}\geq \cdots$. Alors $p$ est inférieur ou égal à $q$ dans l'ordre de domination, et on écrit $p\trianglelefteq q$ si, pour tout $k\geq 1$, la somme des $k$ parties les plus grandes de $p$ est inférieure ou égale à la somme des $k$ plus grandes parties de $q$. Formellement : $p\trianglelefteq q$ si et seulement si, pour tout $k\geq 1$, $p_{1}+\cdots +p_{k}\leq q_{1}+\cdots +q_{k}.$

Dans cette définition, les partitions sont allongées si nécessaire en les complétant de parties nulles. Par exemple, et comme indiqué dans la figure, on a $(6)\trianglerighteq (5,1)\trianglerighteq (4,2)\trianglerighteq \cdots \trianglerighteq (1,1,1,1,1,1)$.

Propriétés de l'ordre de domination

• Parmi les partitions d'un entier $n$, la partition $(1,\ldots ,1)$ est la plus petite, et $(n)$ la plus grande.
• L'ordre de domination implique l'ordre lexicographique. En d'autres termes, si $p$ domine $q$, alors $p$ est supérieur à $q$ dans l'ordre lexicographique, mais la réciproque n'est pas vraie : par exemple $(4,1,1)$ et $(3,3)$ sont incomparables pour l'ordre de domination alors que la première est lexicographiquement plus grande que la deuxième.
• L'ensemble partiellement ordonné des partitions de $n$ est totalement ordonné (et l'ordre de domination et l'ordre lexicographique sont égaux) si et seulement si $n\leq 5$. C'est un ensemble partiellement ordonné gradué (possédant une fonction de rang) si et seulement si $n\leq 6$.
• Une partition $p$ couvre une partition $q$ (c'est-à-dire qu'il n'y a pas d'élémentre entre ces deux, formellement $p\trianglelefteq q$ et $p\trianglelefteq r\trianglelefteq q$ implique $p=r$ ou $q=r$) si et seulement il existe deux indices $i,k$ tels que $q_{j}=p_{j}$ pour $j\neq i,k$, et $p_{i}=q_{i+1},p_{k}=q_{k-1}$; et soit $k=i+1$, soit $q_{k}=q_{i}$.
• Toute partition $p$ possède une partition duale $p^{\star }$ dont le diagramme de Ferrers est le transposé du diagramme de $p$. Cette opération inverse le sens de l'ordre de domination : $p\trianglelefteq q$ si et seulement si $q^{\star }\trianglelefteq p^{\star }.$

Structure de treillis

Les partitions d'un entier $n$ forment un treillis pour l'ordre de domination. L'opération de conjugaison est un antiautomorphisme de ce treillis. On peut décrire les opérations de treillis comme suit :

À une partition $p=(p_{1},p_{2},\ldots )$, complétée éventuellement par des parties nulles, on associe la suite

${\hat {p}}=(0,p_{1},p_{1}+p_{2},\ldots ,p_{1}+p_{2}+\cdots +p_{n}).$

On retrouve $p$ à partir de ${\hat {p}}$ par $p_{i}={\hat {p}}_{i}-{\hat {p}}_{i-1}.$. Par exemple, pour (3,1,1,1) et (2,2,2) les suites associées sont (0,3,4,5,6,6,6) et (0,2,4,6,6,6,6). Les suites associées aux partitions sont caractérisées, parmi les suites à $n+1$ termes, par les trois propriétés suivantes. Elles sont :

• croissantes au sens large : ${\hat {p}}_{i}\leq {\hat {p}}_{i+1}~;$
• concaves : $2{\hat {p}}_{i}\geq {\hat {p}}_{i-1}+{\hat {p}}_{i+1}~;$
• et le premier terme est 0 et le dernier terme est $n$ : ${\hat {p}}_{0}=0,{\hat {p}}_{n}=n.$

Par la définition de l'ordre de domination, une partition $p$ précède une partition $q$ ( $p\trianglelefteq q$) si et seulement si la suite ${\hat {p}}$ est terme par terme inférieure ou égale à ${\hat {q}}$. Il en résulte que la borne inférieure $p\land q$ de deux partitions $p$ et $q$ est la partition dont la suite associée est $\min({\hat {p}}_{i},{\hat {q}}_{i})$. Ainsi, pour les partitions (3,1,1,1) et (2,2,2), la suite associée à leur borne inférieure est (0,2,4,5,6,6,6), et donc $p\land q=(2,2,1,1)$.

Une formule aussi simple n'existe pas pour la borne supérieure parce que le maximum, pris composante par composante, de deux suites concaves n'est plus nécessairement concave: ainsi pour les partitions (3,1,1,1) et (2,2,2) les suites associées sont (0,3,4,5,6,6,6) et (0,2,4,6,6,6,6) et leur maximum, pris terme à terme, est (0,3,4,6,6,6,6) qui n'est pas concave (parce que 2\cdot4<3+6). La construction de la borne supérieure passe par la conjugaison en utilisant l'antiautomorphisme : la borne supérieure $p\lor q$ de $p$ et $q$ est la partition conjuguée de la borne inférieure des conjuguées $p^{\star }$ et $q^{\star }$ :

$p\lor q=(p^{\star }\land q^{\star })^{\star }.$

Pour les deux partitions $p$ et $q$ de l'exemple précédent, leurs partitions conjuguées sont (4,1,1) et (3,3), et leur borne inférieure est (3,2,1). Cette partition est sa propre conjuguée, et la borne supérieure de $p$ et $q$ est donc (3,2,1). Thomas Brylawski a établi d'autres propriétés du treillis des partitions pour l'ordre de domination. Ainsi, le treillis n'est pas distributif dès que $n\geq 7$. En revanche, certaines propriétés des treillis distributifs restent valables dans ce treillis : par exemple, sa fonction de Möbius ne prend que les valeurs 0, 1, et –1.

Voir aussi

• Treillis de Young
• Majorisation

Notes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dominance order » (voir la liste des auteurs).

• (en) Thomas Brylawski, « The lattice of integer partitions », Discrete Mathematics, vol. 6, n^o 3,‎ janvier 1973, p. 201-219 (DOI 10.1016/0012-365X(73)90094-0)
• (en) Ian G. Macdonald, Symmetric functions and Hall polynomials, OUP, coll. « Oxford Mathematical Monographs », 1995, 2^e éd. (ISBN 978-0-19-853489-1, MR 1354144, présentation en ligne)