orden de intervalo

En matemáticas , especialmente en la teoría del orden , el orden de intervalo para una colección de intervalos en la línea real es el orden parcial correspondiente a su relación de precedencia de izquierda a derecha: un intervalo, I ₁ , se considera menor que otro, I ₂ , si I ₁ está completamente a la izquierda de I ₂ . Más formalmente, un poset contable es un orden de intervalo si y solo si existe una biyección de a un conjunto de intervalos reales , tal que para cualquier tenemos en ${\ estilo de visualización P = (X, \ leq)}$${\ estilo de visualización X}$${\displaystyle x_{i}\mapsto (\ell _{i},r_{i})}$${\ estilo de visualización x_ {i}, x_ {j} \ en X}$${\displaystyle x_{i}<x_{j}}$${\ estilo de visualización P}$exactamente cuando Dichos conjuntos pueden caracterizarse de manera equivalente como aquellos sin subconjuntos inducidos isomorfos al par de cadenas de dos elementos , en otras palabras, como los conjuntos libres. ^[1]${\displaystyle r_{i}<\ell _{j}}$${\ estilo de visualización (2+2)}$

La subclase de órdenes interválicos que se obtiene restringiendo los intervalos a los de longitud unitaria, para que todos tengan la forma , son precisamente los semiórdenes .${\displaystyle (\ell_{i},\ell_{i}+1)}$

El complemento del gráfico de comparabilidad de un orden de intervalo ( , ≤) es el gráfico de intervalo .${\ estilo de visualización X}$ ${\ estilo de visualización (X, \ mayúscula)}$

Los órdenes de intervalo no deben confundirse con los órdenes de contención de intervalo, que son los órdenes de inclusión en intervalos en la línea real (equivalentemente, los órdenes de dimensión ≤ 2).

Un parámetro importante de las órdenes parciales es la dimensión de la orden : la dimensión de una orden parcial es el menor número de órdenes lineales cuya intersección es . Para órdenes de intervalo, la dimensión puede ser arbitrariamente grande. Y aunque se sabe que el problema de determinar la dimensión de órdenes parciales generales es NP-difícil , determinar la dimensión de un orden de intervalo sigue siendo un problema de complejidad computacional desconocida . ^[2]${\ estilo de visualización P}$${\ estilo de visualización P}$

Un orden parcial en el conjunto { a , b , c , d , e , f } ilustrado por su diagrama de Hasse (izquierda) y una colección de intervalos que lo representa (derecha).

El poset (diagrama de Hasse negro) no puede ser parte de un orden de intervalo: si a está completamente a la derecha de b , y d se superpone tanto con a como con b , y c está completamente a la derecha de d , entonces c debe estar completamente a la derecha de b (luz borde gris).${\ estilo de visualización (2+2)}$