Accueil🇫🇷Chercher

Ordre de domination

En mathématiques discrètes, l’ordre de domination (en anglais dominance order, appelé aussi dominance ordering, majorization order, natural ordering[1]) 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 et deux partitions d'un entier , avec et . Alors est inférieur ou égal à dans l'ordre de domination, et on écrit si, pour tout , la somme des parties les plus grandes de est inférieure ou égale à la somme des plus grandes parties de . Formellement : si et seulement si, pour tout ,

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 .

Propriétés de l'ordre de domination[1]

  • Parmi les partitions d'un entier , la partition est la plus petite, et la plus grande.
  • L'ordre de domination implique l'ordre lexicographique. En d'autres termes, si domine , alors est supérieur à dans l'ordre lexicographique, mais la réciproque n'est pas vraie : par exemple et 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 est totalement ordonné (et l'ordre de domination et l'ordre lexicographique sont égaux) si et seulement si . C'est un ensemble partiellement ordonné gradué (possédant une fonction de rang) si et seulement si .
  • Une partition couvre une partition (c'est-à-dire qu'il n'y a pas d'élémentre entre ces deux, formellement et implique ou ) si et seulement il existe deux indices tels que pour , et ; et soit , soit [2].
  • Toute partition possède une partition duale dont le diagramme de Ferrers est le transposé du diagramme de . Cette opération inverse le sens de l'ordre de domination : si et seulement si

Structure de treillis

Les partitions d'un entier 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 , complétée éventuellement par des parties nulles, on associe la suite

On retrouve à partir de par . 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 à termes, par les trois propriétés suivantes. Elles sont :

  • croissantes au sens large :
  • concaves :
  • et le premier terme est 0 et le dernier terme est :

Par la définition de l'ordre de domination, une partition précède une partition ( ) si et seulement si la suite est terme par terme inférieure ou égale à . Il en résulte que la borne inférieure de deux partitions et est la partition dont la suite associée est . 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 .

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 de et est la partition conjuguée de la borne inférieure des conjuguées et :

Pour les deux partitions et 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 et est donc (3,2,1). Thomas Brylawski[3] 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 . 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

Notes

  1. Macdonald 1979, Section I.1, p. 5-7.
  2. Brylawski 1973, Prop. 2.3.
  3. Brylawski 1973.
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.