Dimension de l'ordre

En mathématiques , la dimension d'un ensemble partiellement ordonné (ou poset) est le plus petit nombre d' ordres totaux dont l' intersection donne lieu à cet ordre partiel. Ce concept est également parfois appelé dimension d'ordre ou dimension de Dushnik-Miller de l'ordre partiel.

des extensions linéaires de telles que, pour tout et dans , précède dans si et seulement si elle précède dans toutes les extensions linéaires, s'il en existe. Autrement dit, l'intersection de ces extensions linéaires est égale à . C'est-à-dire,

Une autre définition de la dimension de commande est le nombre minimal de commandes totales tel que P s'intègre dans leur produit avec un ordre par composant, c'est-à-dire si et seulement si pour tout i (

,

c'est-à-dire que pour tout et dans , précisément lorsque ,..., . Ainsi, une définition équivalente de la dimension d'un poset est « la plus petite cardinalité d'un réalisateur de ».

On peut démontrer que toute famille non vide d'extensions linéaires est un réalisateur d'un ensemble partiellement ordonné fini si et seulement si, pour chaque paire critique de , pour un certain ordre dans .

Soit n un entier positif, et soit P l'ordre partiel sur les éléments a _{_i} et b _{_i} (pour 1 ≤ i ≤ n ) tel que a _{_i} ≤ b _{_j} dès que i ≠ j , mais qu'aucune autre paire ne soit comparable. En particulier, a _{_i} et b_{_i} sont incomparables dans P ; P peut être vu comme une forme orientée d'un graphe couronne . L'illustration montre un ordre de ce type pour n = 4.

Alors, pour chaque i , tout réalisateur doit contenir un ordre linéaire qui commence par tous les a _{_j} sauf a _{_i} (dans un certain ordre), puis inclut b_{_i} , puis a _{_i}, et se termine par tous les b_{_j} restants . En effet, si un réalisateur ne contenait pas un tel ordre, l'intersection de ses ordres aurait a _{_i} précédant b_{_i} , ce qui contredirait l'incomparabilité de a _{_i} et b _{_i} dans P. Réciproquement, toute famille d'ordres linéaires qui inclut un ordre de ce type pour chaque i a P comme intersection. Ainsi, P est de dimension exactement n . En fait, P est connu comme l' exemple standard d'un ensemble partiellement ordonné de dimension n , et est généralement noté S_{_n} .

Les ordres partiels de dimension deux peuvent être caractérisés comme les ordres partiels dont le graphe de comparabilité est complémentaire de celui d'un autre ordre partiel Baker, Fishburn & Roberts, 1971 ) . Autrement dit, P est un ordre partiel de dimension deux si et seulement s'il existe un ordre partiel Q sur le même ensemble d'éléments, tel que toute paire x , y d'éléments distincts soit comparable dans un seul de ces deux ordres partiels. Si P est réalisé par deux prolongements linéaires, alors l'ordre partiel Q complémentaire de P peut être réalisé en inversant l'un des deux prolongements. Par conséquent, les graphes de comparabilité des ordres partiels de dimension deux sont précisément les graphes de permutation , c'est-à-dire des graphes qui sont à la fois des graphes de comparabilité et complémentaires de graphes de comparabilité.

Les ordres partiels de dimension deux comprennent les ordres partiels série-parallèle Valdes, Tarjan et Lawler 1982 ) . Ce sont précisément les ordres partiels dont les diagrammes de Hasse possèdent des dessins de dominance , que l'on peut obtenir en utilisant les positions dans les deux permutations d'un réalisateur comme coordonnées cartésiennes.

Il est possible de déterminer en temps polynomial si un ensemble fini partiellement ordonné donné a une dimension d'ordre inférieure ou égale à deux, par exemple en vérifiant si le graphe de comparabilité de l'ordre partiel est un graphe de permutation. Cependant, pour tout k ≥ 3, tester si la dimension d'ordre est inférieure ou égale à k est un problème NP-complet Yannakakis 1982 ) .

L' ensemble partiellement ordonné d'incidence d'un graphe non orienté G a pour éléments les sommets et les arêtes de G ; dans cet ensemble, x ≤ y si x = y ou si x est un sommet, y une arête et x une extrémité de y . Certains types de graphes peuvent être caractérisés par la dimension d'ordre de leur ensemble partiellement ordonné d'incidence : un graphe est un graphe de chemin si et seulement si la dimension d'ordre de son ensemble partiellement ordonné d'incidence est au plus égale à deux, et d'après le théorème de Schnyder , il est un graphe planaire si et seulement si la dimension d'ordre de son ensemble partiellement ordonné d'incidence est au plus égale à trois Schnyder 1989 ) .

Pour un graphe complet à n sommets, la dimension d'ordre de l'ensemble partiellement ordonné d'incidence est Hoşten & Morris 1999 ) . Il s'ensuit que tous les graphes simples à n sommets ont des ensembles partiellement ordonnés d'incidence de dimension d'ordre .

Une généralisation de la notion de dimension est la k -dimension (notée k_k ), qui correspond au nombre minimal de chaînes de longueur au plus k dans le produit desquelles l'ordre partiel peut être plongé. En particulier, la 2-dimension d'un ordre peut être vue comme la taille du plus petit ensemble tel que l'ordre se plonge dans l' ordre d'inclusion sur cet ensemble.