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 1 , se considera menor que otro, I 2 , si I 1 está completamente a la izquierda de I 2 . 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, por lo que , tal que para cualquier tenemos en Exactamente cuando . Dichos posets pueden caracterizarse de manera equivalente como aquellos sin subposet inducidos isomorfos al par de cadenas de dos elementos , en otras palabras como el-Posets gratis. [1]
La subclase de órdenes de intervalo obtenida al restringir los intervalos a los de longitud unitaria, por lo que todos tienen la forma , son precisamente los semiorders .
El complemento del gráfico de comparabilidad de un orden de intervalo (, ≤) es el gráfico de intervalo .
Las órdenes de intervalo no deben confundirse con las órdenes de contención de intervalo, que son las órdenes de inclusión en intervalos en la línea real (de manera equivalente, las órdenes de dimensión ≤ 2).
Órdenes de intervalo y dimensión
¿Cuál es la complejidad de determinar la dimensión de orden de un orden de intervalo?
Un parámetro importante de los pedidos parciales es la dimensión del pedido : la dimensión de un pedido parciales 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]
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. Así, la dimensión de intervalo de un conjunto parcialmente ordenadoes el menor número entero para los que existen órdenes de intervalo en con Exactamente cuando y . La dimensión de intervalo de un pedido nunca es mayor que su dimensión de pedido. [3]
Combinatoria
Además de ser isomorfo a -puestos gratuitos, pedidos de intervalo sin etiqueta en también están en biyección con un subconjunto de involuciones libres de punto fijo en conjuntos ordenados con cardinalidad . [4] Estas son las involuciones sin los llamados anidamientos de vecinos izquierdos o derechos donde, para cualquier involución en , un anidamiento a la izquierda es un tal que y un correcto anidamiento es un tal que .
Tales involuciones, de acuerdo con la semi-longitud, tienen una función generadora ordinaria [5]
El coeficiente de en la expansión de da el número de órdenes de tamaño de intervalo sin etiquetar . Comienza la secuencia de estos números (secuencia A022493 en la OEIS )
- 1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642,…
Notas
Referencias
- Bousquet-Mélou, Mireille ; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010), "(2 + 2) posets libres, secuencias de ascenso y patrones que evitan las permutaciones", Journal of Combinatorial Theory , Serie A, 117 (7): 884–909, arXiv : 0806.0666 , doi : 10.1016 / j .jcta.2009.12.007 , MR 2.652.101 , S2CID 8677150.
- Felsner, S. (1992), Órdenes de intervalo: Estructura combinatoria y algoritmos (PDF) , Ph.D. disertación, Universidad Técnica de Berlín.
- Felsner, S .; Habib, M .; Möhring, RH (1994), "Sobre la interacción entre la dimensión del 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", Topología , 40 (5): 945–960, doi : 10.1016 / s0040-9383 (00) 00005-7 , MR 1860536.
Otras lecturas
- Fishburn, Peter (1985), Órdenes de intervalo y gráficos de intervalo: un estudio de conjuntos ordenados parcialmente , John Wiley