En matemáticas , la dimensión de un conjunto parcialmente ordenado (poset) es el número más pequeño de los pedidos totales la intersección de las cuales da lugar a la 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) estudiaron por primera vez la dimensión del orden; para un tratamiento más detallado de este tema que el proporcionado aquí, ver Trotter (1992) .
Definicion formal
La dimensión de un poset P es el menor número entero t para el que existe una familia
de extensiones lineales de P para que, por cada x y y en P , x precede y en P si y sólo si precede y en todas las extensiones lineales. Es decir,
Una definición alternativa de dimensión de pedido es el número mínimo de pedidos totales, de modo que P se integra en su producto con ordenamiento por componentes, es decir si y solo si para todo i ( Hiraguti 1955 , Milner y Pouzet 1990 ).
Realizadores
Una familia de órdenes lineales en X se llama un realizador de un poset P = ( X , < P ) si
- ,
que es decir que para cualquier x y y en X , x < P y precisamente cuando x < 1 y , x < 2 y , ..., y x < t y . Por tanto, una definición equivalente de la dimensión de un poset P es "la mínima cardinalidad de un realizador de P ".
Se puede demostrar que cualquier familia R no vacía de extensiones lineales es un materializador de un conjunto finito parcialmente ordenado P si y solo si, para cada par crítico ( x , y ) de P , y < i x para algún orden < i en R .
Ejemplo
Sea n un número 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 gráfico 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 incluye b i , luego a i , y termina con todos los b j restantes . Esto es así porque si hubiera un realizador que no incluya tal orden, entonces la intersección de las órdenes de que Realizer tendría un i precedente b i , lo que contradice la incomparabilidad de un 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 tanto, P tiene una dimensión exactamente n . De hecho, P se conoce como el ejemplo estándar de un conjunto de dimensiones n , y generalmente se denota por S n .
Pedir dimensión dos
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, de modo que cada par x , y de elementos distintos es comparable exactamente en uno de estos dos órdenes parciales. Si P se realiza mediante dos extensiones lineales, entonces el orden parcial Q complementario de P puede realizarse invirtiendo una de las dos extensiones lineales. Por lo tanto, los gráficos de comparabilidad de los órdenes parciales de la dimensión dos son exactamente los gráficos de permutación , gráficos que son en sí mismos gráficos de comparabilidad y complementarios a los gráficos de comparabilidad.
Los órdenes parciales de orden dimensión dos incluyen los órdenes parciales serie-paralelos ( Valdés, 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.
Complejidad computacional
Es posible determinar en tiempo polinomial si un conjunto finito parcialmente ordenado dado tiene una dimensión de orden como máximo dos, por ejemplo, probando 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 probar si la dimensión del orden es como máximo k ( Yannakakis 1982 ).
Posets de incidencia de gráficos
El poset de incidencia de cualquier grafo no dirigido G tiene los vértices y aristas de G como sus elementos; en este conjunto, x ≤ y si x = y o x es un vértice, y es una arista y x es un punto final de y . Ciertos tipos de gráficos pueden caracterizarse por las dimensiones de orden de sus posiciones de incidencia: una gráfica es una gráfica de trayectoria si y solo si la dimensión de orden de su posición de incidencia es como máximo dos, y según el teorema de Schnyder es una gráfica plana si y sólo si la dimensión de orden de su posición de incidencia es como máximo tres ( Schnyder 1989 ).
Para un gráfico completo en n vértices, la dimensión de orden del conjunto de incidencia es( Hoşten y Morris 1999 ). De ello se deduce que todos los gráficos simples de n -vértices tienen posiciones de incidencia con dimensión de orden.
k -dimensión y 2-dimensión
Una generalización de dimensión es la noción de dimensión k (escrita) que es el número mínimo de cadenas de longitud como máximo k en cuyo producto se puede incrustar el orden parcial. En particular, la dimensión bidimensional de un pedido puede verse como el tamaño del conjunto más pequeño, de modo que el pedido se incrusta en el orden de inclusión de este conjunto.
Ver también
Referencias
- Baker, KA; Fishburn, P .; Roberts, FS (1971), "Órdenes parciales de dimensión 2", Networks , 2 (1): 11-28, doi : 10.1002 / net.3230020103.
- Dushnik, Ben; Miller, EW (1941), "Conjuntos parcialmente ordenados", American Journal of Mathematics , 63 (3): 600–610, doi : 10.2307 / 2371374 , hdl : 10338.dmlcz / 100377 , JSTOR 2371374.
- Hiraguti, Tosio (1955), "Sobre la dimensión de las órdenes" (PDF) , Los informes científicos de la Universidad de Kanazawa , 4 (1): 1–20, MR 0077500.
- Hoşten, Serkan; Morris, Walter D., Jr. (1999), "The order dimension of the complete graph", Discrete Mathematics , 201 (1-3): 133-139, doi : 10.1016 / S0012-365X (98) 00315-X , Señor 1687882.
- Milner, EC; Pouzet, M. (1990), "Una nota sobre la dimensión de un poset", Orden , 7 (1): 101–102, doi : 10.1007 / BF00383178 , MR 1086132 , S2CID 123485792.
- Schnyder, W. (1989), "Gráficos planos y dimensión poset", Order , 5 (4): 323–343, doi : 10.1007 / BF00353652 , S2CID 122785359.
- Trotter, William T. (1992), Combinatoria y conjuntos parcialmente ordenados: teoría de la dimensión , Johns Hopkins Series in the Mathematical Sciences, The Johns Hopkins University Press, ISBN 978-0-8018-4425-6.
- Valdés, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982), "El reconocimiento de dígrafos paralelos en serie", SIAM Journal on Computing , 11 (2): 298–313, doi : 10.1137 / 0211023.
- Yannakakis, Mihalis (1982), "La complejidad del problema de dimensión de orden parcial", SIAM Journal on Algebraic and Discrete Methods , 3 (3): 351–358, doi : 10.1137 / 0603036.