politopo de orden

En matemáticas, el politopo de orden de un conjunto parcialmente ordenado finito es un politopo convexo definido a partir de dicho conjunto. Los puntos del politopo de orden son las funciones monótonas del conjunto dado al intervalo unitario , sus vértices corresponden a los conjuntos superiores del orden parcial y su dimensión es el número de elementos en el orden parcial. El politopo de orden es un politopo distributivo , lo que significa que los mínimos y máximos de pares de sus puntos, coordenados, permanecen dentro del politopo.

El politopo de orden de un orden parcial debe distinguirse del politopo de ordenación lineal , un politopo definido a partir de un número${\displaystyle n}$como la envoltura convexa de los vectores indicadores de los conjuntos de aristas de${\displaystyle n}$Torneos transitivos de vértices . ^{[ 1 ]}

Un conjunto parcialmente ordenado es un par${\displaystyle (S,\leq )}$dónde${\displaystyle S}$es un conjunto arbitrario y${\displaystyle \leq }$es una relación binaria en pares de elementos de${\displaystyle S}$eso es reflexivo (para todos)${\displaystyle x\in S}$,${\displaystyle x\leq x}$), antisimétrico (para todos${\displaystyle x,y\in S}$con${\displaystyle x\neq y}$como máximo uno de${\displaystyle x\leq y}$y${\displaystyle y\leq x}$puede ser cierto), y transitivo (para todo${\displaystyle x,y,z\in S}$, si${\displaystyle x\leq y}$y${\displaystyle y\leq z}$entonces${\displaystyle x\leq z}$).

Un conjunto parcialmente ordenado${\displaystyle (S,\leq )}$Se dice que es finito cuando${\displaystyle S}$es un conjunto finito . En este caso, la colección de todas las funciones${\displaystyle f}$ese mapa${\displaystyle S}$La suma de funciones punto por punto de los números reales forma un espacio vectorial de dimensión finita , con la suma de funciones como operación de suma vectorial. La dimensión del espacio es simplemente el número de elementos de${\displaystyle S}$. El politopo de orden se define como el subconjunto de este espacio que consta de funciones${\displaystyle f}$con las dos propiedades siguientes: ^{[ 2 ] [ 3 ]}

• Por cada${\displaystyle x\in S}$,${\displaystyle 0\leq f(x)\leq 1}$. Eso es,${\displaystyle f}$mapea los elementos de${\displaystyle S}$al intervalo unitario .
• Por cada${\displaystyle x,y\in S}$con${\displaystyle x\leq y}$,${\displaystyle f(x)\leq f(y)}$. Eso es,${\displaystyle f}$es una función monótona

Por ejemplo, para un conjunto parcialmente ordenado que consta de dos elementos.${\displaystyle x}$y${\displaystyle y}$, con${\displaystyle x\leq y}$en el orden parcial, las funciones${\displaystyle f}$Desde estos puntos se pueden identificar números reales con puntos${\displaystyle (f(x),f(y))}$en el plano cartesiano . Para este ejemplo, el politopo de orden consta de todos los puntos en el${\displaystyle (x,y)}$-avión con${\displaystyle 0\leq x\leq y\leq 1}$. Este es un triángulo rectángulo isósceles con vértices en (0,0), (0,1) y (1,1).

Los vértices del politopo de orden consisten en funciones monótonas de${\displaystyle S}$a${\displaystyle \{0,1\}}$Es decir, el politopo de orden es un politopo entero ; no tiene vértices con coordenadas fraccionarias . Estas funciones son precisamente las funciones indicadoras de los conjuntos superiores del orden parcial. Por lo tanto, el número de vértices es igual al número de conjuntos superiores. ^{[ 2 ]}

Las facetas del politopo de orden son de tres tipos: ^{[ 2 ]}

• Desigualdades${\displaystyle 0\leq f(x)}$para cada elemento mínimo${\displaystyle x}$del conjunto parcialmente ordenado,
• Desigualdades${\displaystyle f(y)\leq 1}$para cada elemento máximo${\displaystyle y}$del conjunto parcialmente ordenado, y
• Desigualdades${\displaystyle f(x)\leq f(y)}$para cada dos elementos distintos${\displaystyle x,y}$que no tienen un tercer elemento distinto${\displaystyle z}$entre ellos; es decir, para cada par${\displaystyle (x,y)}$en la relación de recubrimiento del conjunto parcialmente ordenado.

Las facetas pueden considerarse de una manera más simétrica mediante la introducción de elementos especiales.${\displaystyle \bot }$debajo de todos los elementos en el orden parcial y${\displaystyle \top }$por encima de todos los elementos, mapeados por${\displaystyle f}$a 0 y 1 respectivamente, y manteniendo solo desigualdades del tercer tipo para el conjunto parcialmente ordenado aumentado resultante. ^{[ 2 ]}

De manera más general, con el mismo aumento por${\displaystyle \bot }$y${\displaystyle \top }$Las caras de todas las dimensiones del politopo de orden se corresponden biunívocamente con los cocientes del orden parcial. Cada cara es congruente con el politopo de orden del cociente de orden parcial correspondiente. ^{[ 2 ]}

El politopo de orden de un orden lineal es un tipo especial de símplex llamado símplex de orden u ortoesquema . Cada punto del cubo unitario cuyas coordenadas son todas distintas se encuentra en uno único de estos ortoesquemas, el símplex de orden para el orden lineal de sus coordenadas. Debido a que estos símplexes de orden son todos congruentes entre sí y (para órdenes en${\displaystyle n}$elementos) hay${\displaystyle n!}$diferentes órdenes lineales, el volumen de cada simplex de orden es${\displaystyle 1/n!}$. ^{[ 2 ] [ 3 ]} De manera más general, un politopo de orden puede particionarse en símplices de orden de forma canónica, con un símplice para cada extensión lineal del conjunto parcialmente ordenado correspondiente. ^{[ 2 ]} Por lo tanto, el volumen de cualquier politopo de orden es${\displaystyle 1/n!}$multiplicado por el número de extensiones lineales del conjunto parcialmente ordenado correspondiente. ^{[ 2 ] [ 3 ]} Esta conexión entre el número de extensiones lineales y el volumen puede usarse para aproximar eficientemente el número de extensiones lineales de cualquier orden parcial (a pesar de que calcular este número exactamente es #P-completo ) aplicando un esquema de aproximación aleatorio de tiempo polinomial para el volumen del politopo. ^{[ 4 ]}

El polinomio de Ehrhart del politopo de orden es un polinomio cuyos valores en valores enteros${\displaystyle x}$da el número de puntos enteros en una copia del politopo escalada por un factor de${\displaystyle x}$Para el politopo ordenado, el polinomio de Ehrhart es igual (tras un pequeño cambio de variables) al polinomio ordenado del conjunto parcialmente ordenado correspondiente. Este polinomio codifica varias piezas de información sobre el politopo, incluyendo su volumen (el coeficiente principal del polinomio) y su número de vértices (la suma de los coeficientes). ^{[ 2 ] [ 3 ]}

Según el teorema de representación de Birkhoff para retículos distributivos finitos , los conjuntos superiores de cualquier conjunto parcialmente ordenado forman un retículo distributivo finito, y todo retículo distributivo finito puede representarse de esta manera. ^{[ 5 ]} Los conjuntos superiores corresponden a los vértices del politopo de orden, por lo que la aplicación de los conjuntos superiores a los vértices proporciona una representación geométrica de cualquier retículo distributivo finito. Bajo esta representación, las aristas del politopo conectan elementos comparables del retículo.

Si dos funciones${\displaystyle p}$y${\displaystyle q}$ambos pertenecen al politopo de orden de un conjunto parcialmente ordenado.${\displaystyle (S,\leq )}$, entonces la función${\displaystyle p\wedge q}$que mapas${\displaystyle x}$a${\displaystyle \min(p(x),q(x))}$y la función${\displaystyle p\vee q}$ que mapas${\displaystyle x}$a${\displaystyle \max(p(x),q(x))}$Ambos también pertenecen al politopo de orden. Las dos operaciones${\displaystyle \wedge }$y${\displaystyle \vee }$Se le da al politopo de orden la estructura de un retículo distributivo continuo , dentro del cual se encuentra incrustado el retículo distributivo finito del teorema de Birkhoff. Es decir, todo politopo de orden es un politopo distributivo . Los politopos distributivos con todas las coordenadas de vértice iguales a 0 o 1 son precisamente los politopos de orden. ^{[ 6 ]}