Ordenar politopo

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

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

Definición y ejemplo

Un conjunto parcialmente ordenado es un par donde es un conjunto arbitrario y es una relación binaria en pares de elementos de que es reflexiva (para todos , ), antisimétrica (para todos con como máximo uno de y puede ser verdadero) y transitiva (para todos , si y entonces ). ${\displaystyle (S,\leq )}$ ${\displaystyle S}$ ${\displaystyle \leq }$ ${\displaystyle S}$ ${\displaystyle x\in S}$ ${\displaystyle x\leq x}$ ${\displaystyle x,y\in S}$ ${\displaystyle x\neq y}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq x}$ ${\displaystyle x,y,z\in S}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq z}$ ${\displaystyle x\leq z}$

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

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

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

Vértices y facetas

Los vértices del politopo de orden consisten en funciones monótonas de a . Es decir, el politopo de orden es un politopo entero ; no tiene vértices con coordenadas fraccionarias. Estas funciones son exactamente 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] ${\displaystyle S}$ ${\displaystyle \{0,1\}}$

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

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

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

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

Volumen y polinomio de Ehrhart

El politopo de orden de un orden lineal es un tipo especial de símplex llamado símplex de orden u ortosquema . Cada punto del cubo unitario cuyas coordenadas son todas distintas se encuentra en uno único de estos ortosquemas, el símplex de orden para el orden lineal de sus coordenadas. Debido a que estos símplex de orden son todos congruentes entre sí y (para órdenes de elementos) hay diferentes órdenes lineales, el volumen de cada símplex de orden es . ^{[2] [3]} De manera más general, un politopo de orden se puede dividir en símplex de orden de manera canónica, con un símplex para cada extensión lineal del conjunto parcialmente ordenado correspondiente. ^[2] Por lo tanto, el volumen de cualquier politopo de orden se multiplica 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 se puede utilizar para aproximar el número de extensiones lineales de cualquier orden parcial de manera eficiente (a pesar del hecho de que calcular este número exactamente es #P-completo ) aplicando un esquema de aproximación de tiempo polinomial aleatorio para el volumen del politopo. ^[4] ${\displaystyle n}$ ${\displaystyle n!}$ ${\displaystyle 1/n!}$ ${\displaystyle 1/n!}$

El polinomio de Ehrhart del politopo de orden es un polinomio cuyos valores en valores enteros dan el número de puntos enteros en una copia del politopo escalada por un factor de . Para el politopo de orden, el polinomio de Ehrhart es igual (después de un cambio menor de variables) al polinomio de orden del conjunto parcialmente ordenado correspondiente. Este polinomio codifica varios datos sobre el politopo, incluido su volumen (el coeficiente principal del polinomio y su número de vértices (la suma de los coeficientes). ^{[2] [3]} ${\displaystyle x}$ ${\displaystyle x}$

Celosía continua

Por el teorema de representación de Birkhoff para redes distributivas finitas , los conjuntos superiores de cualquier conjunto parcialmente ordenado forman una red distributiva finita, y cada red distributiva finita 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 red distributiva finita. Bajo esta representación, los bordes del politopo conectan elementos comparables de la red.

Si dos funciones y ambas pertenecen al politopo de orden de un conjunto parcialmente ordenado , entonces la función que se asigna a , y la función que se asigna a ambas también pertenecen al politopo de orden. Las dos operaciones y dan al politopo de orden la estructura de una red distributiva continua , dentro de la cual está inserta la red distributiva finita del teorema de Birkhoff. Es decir, cada politopo de orden es un politopo distributivo . Los politopos distributivos con todas las coordenadas de vértice iguales a 0 o 1 son exactamente los politopos de orden. ^[6] ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle (S,\leq )}$ ${\displaystyle p\wedge q}$ ${\displaystyle x}$ ${\displaystyle \min(p(x),q(x))}$ ${\displaystyle p\vee q}$ ${\displaystyle x}$ ${\displaystyle \max(p(x),q(x))}$ ${\displaystyle \wedge }$ ${\displaystyle \vee }$

Referencias

1. Grötschel, Martin ; Jünger, Michael; Reinelt, Gerhard (1985), "Facetas del politopo de ordenamiento lineal", Programación matemática , 33 (1): 43–60, doi :10.1007/BF01582010, MR  0809748, S2CID  21071064
2. Stanley, Richard P. (1986), "Dos politopos poset", Geometría discreta y computacional , 1 (1): 9–23, doi : 10.1007/BF02187680 , MR  0824105
3. Stanley, Richard (2011), Combinatoria enumerativa, volumen 1, segunda edición, versión del 15 de julio de 2011 (PDF) , pp. 571–572, 645
4. Brightwell, Graham ; Winkler, Peter (1991), "Conteo de extensiones lineales", Order , 8 (3): 225–242, doi :10.1007/BF00383444, MR  1154926, S2CID  119697949
5. Birkhoff, Garrett (1937), "Anillos de conjuntos", Duke Mathematical Journal , 3 (3): 443–454, doi :10.1215/S0012-7094-37-00334-X
6. Felsner, Stefan; Knauer, Kolja (2011), "Redes distributivas, poliedros y flujos generalizados", European Journal of Combinatorics , 32 (1): 45–59, doi : 10.1016/j.ejc.2010.07.011 , MR  2727459. Véase en particular la Observación 11, pág. 53.