En matemáticas , la dimensión de un conjunto parcialmente ordenado (poset) es el número más pequeño de órdenes totales cuya intersección da lugar al orden parcial. Este concepto también se denomina a veces dimensión de orden o dimensión de Dushnik-Miller del orden parcial. Dushnik y Miller (1941) fueron los primeros en estudiar la dimensión de orden; para un tratamiento más detallado de este tema que el que se ofrece aquí, véase Trotter (1992).
La dimensión de un poset P es el menor entero t para el que existe una familia
de extensiones lineales de P de modo que, para cada x e y en P , x precede a y en P si y solo si precede a y en todas las extensiones lineales, si existe alguna t de ese tipo . Es decir,
Una definición alternativa de la dimensión del orden es el número mínimo de órdenes totales tales que P se incorpora a su producto con ordenamiento por componentes, es decir, si y sólo si para todos los i (Hiraguti 1955, Milner y Pouzet 1990).
Una familia de órdenes lineales en X se denomina realizador de un conjunto poset P = ( X , < P ) si
es decir que para cualquier x e y en X , x < P y precisamente cuando x < 1 y , x < 2 y , ..., y x < t y . Por lo tanto, una definición equivalente de la dimensión de un conjunto parcial P es "la menor cardinalidad de un realizador de P ".
Se puede demostrar que cualquier familia no vacía R de extensiones lineales es un realizador de un conjunto finito parcialmente ordenado P si y sólo si, para cada par crítico ( x , y ) de P , y < i x para algún orden < i en R .
Sea n un entero positivo y sea P el orden parcial de los elementos a i y b i (para 1 ≤ i ≤ n ) en el que a i ≤ b j siempre que i ≠ j , pero ningún otro par es comparable. En particular, a i y b i son incomparables en P ; P puede verse como una forma orientada de un grafo de corona . La ilustración muestra un ordenamiento de este tipo para n = 4.
Entonces, para cada i , cualquier realizador debe contener un orden lineal que comience con todos los a j excepto a i (en algún orden), luego incluya b i , luego a i , y termine con todos los b j restantes . Esto es así porque si hubiera un realizador que no incluyera tal orden, entonces la intersección de los órdenes de ese realizador tendría a i precediendo a b i , lo que contradeciría la incomparabilidad de a i y b i en P . Y a la inversa, cualquier familia de órdenes lineales que incluya un orden de este tipo para cada i tiene P como su intersección. Por lo tanto, P tiene dimensión exactamente n . De hecho, P es conocido como el ejemplo estándar de un conjunto parcial de dimensión n , y generalmente se denota por S n .
Los órdenes parciales con dimensión de orden dos pueden caracterizarse como los órdenes parciales cuyo gráfico de comparabilidad es el complemento del gráfico de comparabilidad de un orden parcial diferente (Baker, Fishburn y Roberts 1971). Es decir, P es un orden parcial con dimensión de orden dos si y solo si existe un orden parcial Q en el mismo conjunto de elementos, tal que cada par x , y de elementos distintos es comparable en exactamente uno de estos dos órdenes parciales. Si P se realiza mediante dos extensiones lineales, entonces el orden parcial Q complementario a P puede realizarse invirtiendo una de las dos extensiones lineales. Por lo tanto, los gráficos de comparabilidad de los órdenes parciales de dimensión dos son exactamente los gráficos de permutación , gráficos que son a la vez gráficos de comparabilidad y complementarios a los gráficos de comparabilidad.
Los órdenes parciales de dimensión de orden dos incluyen los órdenes parciales serie-paralelo (Valdes, Tarjan y Lawler 1982). Son exactamente los órdenes parciales cuyos diagramas de Hasse tienen dibujos de dominancia , que se pueden obtener utilizando las posiciones en las dos permutaciones de un realizador como coordenadas cartesianas.
Es posible determinar en tiempo polinómico si un conjunto finito parcialmente ordenado dado tiene una dimensión de orden de como máximo dos, por ejemplo, comprobando si el gráfico de comparabilidad del orden parcial es un gráfico de permutación. Sin embargo, para cualquier k ≥ 3, es NP-completo comprobar si la dimensión de orden es como máximo k (Yannakakis 1982).
El conjunto de elementos de incidencia de cualquier grafo no dirigido G tiene como elementos los vértices y las aristas de G ; en este conjunto de elementos, x ≤ y si x = y o x es un vértice, y es una arista y x es un extremo de y . Ciertos tipos de grafos pueden caracterizarse por las dimensiones de orden de sus conjuntos de elementos de incidencia: un grafo es un grafo de trayectoria si y solo si la dimensión de orden de su conjunto de elementos de incidencia es como máximo dos, y según el teorema de Schnyder es un grafo plano si y solo si la dimensión de orden de su conjunto de elementos de incidencia es como máximo tres (Schnyder 1989).
Para un grafo completo de n vértices, la dimensión de orden del conjunto parcial de incidencia es (Hoşten y Morris 1999). De ello se deduce que todos los grafos simples de n vértices tienen conjuntos parciales de incidencia con dimensión de orden .
Una generalización de la dimensión es la noción de k -dimensión (escrita como ), que es el número mínimo de cadenas de longitud k como máximo en cuyo producto se puede incluir el orden parcial. En particular, la 2-dimensión de un orden puede verse como el tamaño del conjunto más pequeño tal que el orden se incluye en el orden de inclusión de este conjunto.
