Orden de intervalo

En matemáticas , especialmente en teoría del orden , el orden de intervalos para una colección de intervalos en la recta 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 conjunto parcialmente ordenado numerable${\displaystyle P=(X,\leq )}$es un orden de intervalo si y solo si existe una biyección de${\displaystyle X}$a un conjunto de intervalos reales, por lo tanto${\displaystyle x_{i}\mapsto (\ell _{i},r_{i})}$, de tal manera que para cualquier${\displaystyle x_{i},x_{j}\in X}$tenemos ${\displaystyle x_{i}<x_{j}}$en${\displaystyle P}$exactamente cuando${\displaystyle r_{i}<\ell _{j}}$.

Dichos posets pueden caracterizarse de manera equivalente como aquellos sin subposet inducido isomorfo al par de cadenas de dos elementos , en otras palabras como el${\displaystyle (2+2)}$-propets libres. ^{[ 1 ]} Escrito completamente, esto significa que para cualesquiera dos pares de elementos${\displaystyle a>b}$y${\displaystyle c>d}$uno debe tener${\displaystyle a>d}$o${\displaystyle c>b}$.

La subclase de órdenes de intervalos obtenida al restringir los intervalos a aquellos de longitud unitaria, de modo que todos tengan la forma${\displaystyle (\ell _{i},\ell _{i}+1)}$, son precisamente los semiórdenes .

El complemento del gráfico de comparabilidad de un orden de intervalo (${\displaystyle X}$, ≤) es el gráfico de intervalos${\displaystyle (X,\cap )}$.

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 recta real (o, equivalentemente, los órdenes de dimensión ≤ 2).

Las aplicaciones prácticas de los órdenes de intervalo incluyen la modelización de la evolución de las especies y las historias arqueológicas de los estilos de cerámica. ^{[ 2 ]}

Un parámetro importante de los pedidos parciales es la dimensión del pedido : la dimensión de un pedido parcial.${\displaystyle P}$es el menor número de órdenes lineales cuya intersección es${\displaystyle P}$Para órdenes de intervalo, la dimensión puede ser arbitrariamente grande. Y si bien 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 . ^{[ 3 ]}

Un parámetro relacionado es la dimensión de intervalo , que se define de forma análoga, pero en términos de órdenes de intervalo en lugar de órdenes lineales. Por lo tanto, la dimensión de intervalo de un conjunto parcialmente ordenado${\displaystyle P=(X,\leq )}$es el entero más pequeño${\displaystyle k}$para los cuales existen órdenes de intervalo${\displaystyle \preceq _{1},\ldots ,\preceq _{k}}$en${\displaystyle X}$con${\displaystyle x\leq y}$exactamente cuando${\displaystyle x\preceq _{1}y,\ldots ,}$y${\displaystyle x\preceq _{k}y}$. La dimensión del intervalo de un orden nunca es mayor que su dimensión de orden. ^{[ 4 ]}

Además de ser isomorfo a${\displaystyle (2+2)}$-posets libres, órdenes de intervalo sin etiquetar en${\displaystyle [n]}$también están en biyección con un subconjunto de involuciones sin punto fijo en conjuntos ordenados con cardinalidad${\displaystyle 2n}$ . ^{[ 5 ]} Estas son las involuciones sin los llamados anidamientos de vecinos izquierdos o derechos donde, para cualquier involución ${\displaystyle f}$en${\displaystyle [2n]}$, un anidamiento izquierdo es un${\displaystyle i\in [2n]}$de tal manera que${\displaystyle i<i+1<f(i+1)<f(i)}$y un anidamiento correcto es un${\displaystyle i\in [2n]}$de tal manera que ${\displaystyle f(i)<f(i+1)<i<i+1}$.

Tales involuciones, según la semilongitud, tienen una función generadora ordinaria ^{[ 6 ].}

${\displaystyle F(t)=\sum _{n\geq 0}\prod _{i=1}^{n}(1-(1-t)^{i}).}$

El coeficiente de${\displaystyle t^{n}}$en la expansión de${\displaystyle F(t)}$da el número de órdenes de intervalo sin etiquetar de tamaño${\displaystyle n}$. La secuencia de estos números (secuencia A022493 en el OEIS ) comienza

1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642, …

• Bousquet-Mélou, Mireille ; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010), "(2+2) posets libres, secuencias de ascenso y permutaciones que evitan patrones", Journal of Combinatorial Theory , Serie A, 117 (7): 884–909 , arXiv : 0806.0666 , doi : 10.1016/j.jcta.2009.12.007 , MR 2652101 , S2CID 8677150  .
• Felsner, S. (1992), Órdenes de intervalo: estructura combinatoria y algoritmos (PDF) , Ph.D. disertación, Technische Universität Berlin.
• Felsner, S.; Habib, M.; Möhring, RH (1994), "Sobre la interacción entre la dimensión de intervalo y la dimensión" (PDF) , SIAM Journal on Discrete Mathematics , 7 (1): 32–40 , doi : 10.1137/S089548019121885X , MR 1259007 .
• Fishburn, Peter C. (1970), "Indiferencia intransitiva con intervalos de indiferencia desiguales", Journal of Mathematical Psychology , 7 (1): 144– 149, doi : 10.1016/0022-2496(70)90062-3 , MR 0253942 .
• Zagier, Don (2001), "Invariantes de Vassiliev y una extraña identidad relacionada con la función eta de Dedekind", Topology , 40 (5): 945–960 , doi : 10.1016/s0040-9383(00)00005-7 , MR 1860536 .
• Davey, BA; Priestley, HA (2002) [1990]. Introducción a las redes y el orden (2.ª  ed.). Cambridge University Press. ISBN 9780521784511.

• Fishburn, Peter (1985), Órdenes de intervalos y grafos de intervalos: un estudio de conjuntos parcialmente ordenados , John Wiley