.png/1280px-Symmetric_group_4;_permutohedron_3D;_transpositions_(1-based).png){kind=spacer}
En matemáticas , el permutoedro (también escrito permutaedro ) de orden n es un politopo de ( n − 1) dimensiones incrustado en un espacio de n dimensiones. Sus coordenadas de vértice (etiquetas) son las permutaciones de los primeros n números naturales . Las aristas identifican los caminos más cortos posibles (conjuntos de transposiciones ) que conectan dos vértices (permutaciones). Dos permutaciones conectadas por una arista difieren solo en dos lugares (una transposición ), y los números en estos lugares son vecinos (difieren en valor en 1).
La imagen de la derecha muestra el permutoedro de orden 4, que es el octaedro truncado . Sus vértices son las 24 permutaciones de (1, 2, 3, 4). Los bordes paralelos tienen el mismo color de borde. Los 6 colores de los bordes corresponden a las 6 transposiciones posibles de 4 elementos, es decir, indican en qué dos lugares se diferencian las permutaciones relacionadas. (Por ejemplo, los bordes rojos conectan permutaciones que difieren en los dos últimos lugares).
Según Günter M. Ziegler (1995), los permutoedros fueron estudiados por primera vez por Pieter Hendrik Schoute (1911). El nombre permutoèdre fue acuñado por Georges Th. Guilbaud y Pierre Rosenstiehl (1963). Describen la palabra como bárbara, pero fácil de recordar, y la someten a la crítica de sus lectores. [1]
A veces también se utiliza la ortografía alternativa permut a edro . [2] Los permutoedros a veces se denominan politopos de permutación , pero esta terminología también se utiliza para el politopo relacionado de Birkhoff , definido como la cáscara convexa de las matrices de permutación . De manera más general, V. Joseph Bowman (1972) usa ese término para cualquier politopo cuyos vértices tengan una biyección con las permutaciones de algún conjunto.
El permutoedro de orden n tiene n ! vértices, cada uno de los cuales es adyacente a n − 1 otros. El número de aristas es( norte − 1 ) norte !/2, y su longitud es √ 2 .
Dos vértices conectados se diferencian al intercambiar dos coordenadas, cuyos valores difieren en 1. [3] El par de lugares intercambiados corresponde a la dirección del borde. (En la imagen de ejemplo, los vértices (3, 2, 1, 4) y (2, 3, 1, 4) están conectados por un borde azul y se diferencian intercambiando 2 y 3 en los dos primeros lugares. Los valores 2 y 3 difieren en 1. Todos los bordes azules corresponden a intercambios de coordenadas en los dos primeros lugares).
El número de facetas es 2 n − 2 , porque corresponden a subconjuntos propios no vacíos S de {1 ... n } . Los vértices de una faceta correspondiente al subconjunto S tienen en común que sus coordenadas en lugares de S son más pequeñas que el resto . [4]
De manera más general, las caras de las dimensiones 0 (vértices) a n − 1 (el propio permutoedro) corresponden al ordenamiento débil estricto del conjunto {1 ... n } . Entonces el número de todas las caras es el número de Bell ordenado enésimo . [5] Una cara de dimensión d corresponde a un ordenamiento con k = n − d clases de equivalencia.
El número de caras de dimensión d = n − k en el permutoedro de orden n viene dado por el triángulo T (secuencia A019538 en la OEIS ): con la representación de los números de Stirling de segunda especie
se muestra a la derecha junto con su fila sumas, los números de Bell ordenados .
.png/1280px-Symmetric_group_4;_Cayley_graph_1,2,6_(1-based).png)
El permutoedro es transitivo por vértices : el grupo simétrico S n actúa sobre el permutoedro mediante permutación de coordenadas.
El permutoedro es un zonótopo ; Se puede generar una copia traducida del permutoedro como la suma de Minkowski de los n ( n − 1)/2 segmentos de línea que conectan los pares de vectores de base estándar . [6]
Los vértices y aristas del permutoedro son isomórficos a uno de los gráficos de Cayley del grupo simétrico , es decir, el generado por las transposiciones que intercambian elementos consecutivos. Los vértices del gráfico de Cayley son las permutaciones inversas de las del permutoedro. [7] La imagen de la derecha muestra el gráfico de Cayley de S 4 . Los colores de sus bordes representan las 3 transposiciones generadoras: (1, 2) , (2, 3) , (3, 4)
Este gráfico de Cayley es hamiltoniano ; El algoritmo de Steinhaus-Johnson-Trotter puede encontrar un ciclo hamiltoniano .
El permutoedro de orden n se encuentra completamente en el hiperplano dimensional ( n − 1 ) que consta de todos los puntos cuyas coordenadas suman el número
Además, este hiperplano puede estar formado por infinitas copias traducidas del permutoedro. Cada uno de ellos se diferencia del permutoedro básico por un elemento de una determinada red ( n − 1)-dimensional , que consta de las n -tuplas de números enteros que suman cero y cuyos residuos (módulo n ) son todos iguales:
Esta es la red , la red dual de la red de raíces . En otras palabras, el permutoedro es la célula de Voronoi . En consecuencia, esta red a veces se denomina red permutoédrica. [8]
Por lo tanto, el permutoedro de orden 4 que se muestra arriba mosaico el espacio tridimensional por traslación. Aquí el espacio tridimensional es el subespacio afín del espacio tetradimensional R 4 con coordenadas x , y , z , w que consta de las 4 tuplas de números reales cuya suma es 10,
Se comprueba fácilmente que para cada uno de los siguientes cuatro vectores,
la suma de las coordenadas es cero y todas las coordenadas son congruentes con 1 (mod 4). Tres de estos vectores generan la red de traducción.
Los teselados formados de esta manera a partir de los permutoedros de orden 2, orden 3 y orden 4, respectivamente, son el apeirogon , el mosaico hexagonal regular y el panal cúbico bitruncado . Las teselaciones duales contienen todas las facetas simplex , aunque no son politopos regulares más allá del orden 3.
.png){kind=link}