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 orden politopo son las funciones monotónicas 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 coordinados de pares de sus puntos permanecen dentro del politopo.
El politopo de orden de un orden parcial debe distinguirse del politopo de orden lineal , un politopo definido a partir de un númerocomo el casco convexo de los vectores indicadores de los conjuntos de bordes de-Torneos transitivos de vértice . [1]
Definición y ejemplo
Un conjunto parcialmente ordenado es un par dónde es un conjunto arbitrario y es una relación binaria en pares de elementos de que es reflexivo (para todos , ), antisimétrico (para todos con a lo sumo uno de y puede ser verdadero) y transitivo (para todos , Si y luego ).
Un conjunto parcialmente ordenado se dice que es finito cuando es un conjunto finito . En este caso, la colección de todas las funciones ese mapa a los números reales forma un espacio vectorial de dimensión finita , con la suma puntual de funciones como la operación de suma vectorial. La dimensión del espacio es solo el número de elementos de. El politopo de orden se define como el subconjunto de este espacio que consta de funcionescon las siguientes dos propiedades: [2] [3]
- Para cada , . Es decir, mapea los elementos de al intervalo de la unidad .
- Para cada con , . Es decir,es una función monótona
Por ejemplo, para un conjunto parcialmente ordenado que consta de dos elementos y , con en el orden parcial, las funciones desde estos puntos a números reales se pueden identificar con puntos en el plano cartesiano . Para este ejemplo, el orden politopo 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).
Vértices y facetas
Los vértices del orden politopo consisten en funciones monotónicas de a . Es decir, el politopo de orden es un politopo integral ; 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]
Las facetas del orden politopo son de tres tipos: [2]
- Desigualdades para cada elemento mínimo del conjunto parcialmente ordenado,
- Desigualdades para cada elemento máximo del conjunto parcialmente ordenado, y
- Desigualdades para cada dos elementos distintos que no tienen un tercer elemento distinto entre ellos; es decir, para cada paren la relación de cobertura del conjunto parcialmente ordenado.
Las facetas se pueden considerar de forma más simétrica introduciendo elementos especiales debajo de todos los elementos en el orden parcial y sobre todos los elementos, mapeados por a 0 y 1 respectivamente, y manteniendo solo las desigualdades del tercer tipo para el conjunto aumentado parcialmente ordenado resultante. [2]
De manera más general, con el mismo aumento de y , las caras de todas las dimensiones del orden politopo corresponden 1 a 1 con cocientes del orden parcial. Cada cara es congruente con el orden politopo del correspondiente cociente de orden parcial. [2]
Volumen y polinomio de Ehrhart
El orden politopo de un orden lineal es un tipo especial de simplex llamado orden simplex u ortosquema . Cada punto del cubo unitario cuyas coordenadas son todas distintas se encuentra en uno único de estos ortosquemas, el orden simplex para el orden lineal de sus coordenadas. Debido a que estos orden simples son todos congruentes entre sí y (para órdenes en elementos) hay diferentes órdenes lineales, el volumen de cada orden simplex es. [2] [3] De manera más general, un politopo de orden se puede dividir en orden simple de forma canónica, con un simplex para cada extensión lineal del correspondiente conjunto parcialmente ordenado. [2] Por lo tanto, el volumen de cualquier orden politopo esmultiplicado por el número de extensiones lineales del correspondiente conjunto parcialmente ordenado. [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 de que calcular este número exactamente es # P-completo ) aplicando un valor aleatorio esquema de aproximación de tiempo polinómico para el volumen de politopo. [4]
El polinomio de Ehrhart del orden politopo es un polinomio cuyos valores en valores enteros dar el número de puntos enteros en una copia del politopo escalado 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 correspondiente conjunto parcialmente ordenado. Este polinomio codifica varias piezas de información 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]
Celosía continua
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 cada retículo distributivo finito puede representarse de esta forma. [5] Los conjuntos superiores corresponden a los vértices del orden politopo, por lo que el mapeo de conjuntos superiores a 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 celosía.
Si dos funciones y ambos pertenecen al orden politopo de un conjunto parcialmente ordenado , luego la función que mapas a , y la función que mapas a ambos también pertenecen al orden politopo. Las dos operaciones y dan al politopo de orden la estructura de un retículo distributivo continuo , dentro del cual está incrustado el retículo distributivo finito del teorema de Birkhoff. Es decir, cada politopo de orden es un politopo distributivo . Los politopos distributivos con todas las coordenadas del vértice iguales a 0 o 1 son exactamente del orden politopos. [6]
Referencias
- ^ 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
- ^ a b c d e f g h yo Stanley, Richard P. (1986), "Two poset polytopes", Geometría discreta y computacional , 1 (1): 9-23, doi : 10.1007 / BF02187680 , MR 0824105
- ^ a b c d Stanley, Richard (2011), Enumerative Combinatorics, Volumen 1, segunda edición, versión del 15 de julio de 2011 (PDF) , págs. 571–572, 645
- ^ Brightwell, Graham ; Winkler, Peter (1991), "Contando extensiones lineales", Pedido , 8 (3): 225–242, doi : 10.1007 / BF00383444 , MR 1154926 , S2CID 119697949
- ^ Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215 / S0012-7094-37-00334-X
- ^ Felsner, Stefan; Knauer, Kolja (2011), "Rejillas distributivas, poliedros y flujos generalizados", European Journal of Combinatorics , 32 (1): 45–59, doi : 10.1016 / j.ejc.2010.07.011 , MR 2727459. Ver en particular la Observación 11, p. 53.