.png/1280px-Symmetric_group_4;_permutohedron_3D;_transpositions_(1-based).png){kind=spacer}
En matemáticas , el permutoedro (también escrito permutahedron ) de orden n es un politopo de dimensión ( n − 1) incrustado en un espacio de dimensión n . Las coordenadas de sus vértices (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). Las aristas paralelas tienen el mismo color de arista. Los 6 colores de arista corresponden a las 6 posibles transposiciones de 4 elementos, es decir, indican en qué dos lugares difieren las permutaciones conexas. (Por ejemplo, las aristas rojas conectan permutaciones que difieren en los dos últimos lugares).
Según Günter M. Ziegler (1995), los permutohedros 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). Ellos 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 permutar un edro . [2] A veces, los permutoedros se denominan politopos de permutación , pero esta terminología también se utiliza para el politopo de Birkhoff relacionado , definido como la envoltura convexa de matrices de permutación . De manera más general, V. Joseph Bowman (1972) utiliza ese término para cualquier politopo cuyos vértices tienen 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 más. El número de aristas es ( n − 1) n !/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 de la arista. (En la imagen de ejemplo, los vértices (3, 2, 1, 4) y (2, 3, 1, 4) están conectados por una arista azul y se diferencian al intercambiar 2 y 3 en los primeros dos lugares. Los valores 2 y 3 difieren en 1. Todas las aristas azules corresponden a intercambios de coordenadas en los primeros dos 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 menores que las del resto . [4]
De manera más general, las caras de dimensiones 0 (vértices) a n − 1 (el permutoedro mismo) corresponden a los ordenamientos débiles estrictos del conjunto {1 ... n } . Por lo tanto, el número de todas las caras es el n -ésimo número de Bell ordenado . [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 (sucesión A019538 en la OEIS ): con representando los números de Stirling de segundo tipo
Se muestra a la derecha junto con sus sumas de filas, los números de Bell ordenados .
.png/1280px-Symmetric_group_4;_Cayley_graph_1,2,6_(1-based).png)
El permutoedro es transitivo-vertical : el grupo simétrico S n actúa sobre el permutoedro por permutación de coordenadas.
El permutoedro es un zonotopo ; 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 isomorfos a uno de los grafos de Cayley del grupo simétrico , es decir, el generado por las transposiciones que intercambian elementos consecutivos. Los vértices del grafo de Cayley son las permutaciones inversas de las del permutoedro. [7] La imagen de la derecha muestra el grafo de Cayley de S 4 . Los colores de sus aristas representan las 3 transposiciones generadoras: (1, 2) , (2, 3) , (3, 4)
Este gráfico de Cayley es hamiltoniano ; un ciclo hamiltoniano se puede encontrar mediante el algoritmo de Steinhaus–Johnson–Trotter .
El permutoedro de orden n se encuentra enteramente en el hiperplano ( n − 1 )-dimensional que consiste en todos los puntos cuyas coordenadas suman el número
Además, este hiperplano puede estar recubierto por infinitas copias trasladadas del permutoedro. Cada una de ellas se diferencia del permutoedro básico por un elemento de una determinada red de ( n − 1) dimensiones , que consiste en 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 celda de Voronoi para . En consecuencia, esta red a veces se denomina red permutoédrica. [8]
Así, el permutoedro de orden 4 que se muestra arriba tesela 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 puede comprobar fácilmente que para cada uno de los cuatro vectores siguientes,
La suma de las coordenadas es cero y todas las coordenadas son congruentes con 1 (mód 4). Tres de estos vectores generan la red de traslación.
Las teselaciones formadas de esta manera a partir de los permutoedros de orden 2, orden 3 y orden 4, respectivamente, son el apeirógono , la teselación hexagonal regular y el panal cúbico bitruncado . Las teselaciones duales contienen todas las facetas símplex , aunque no son politopos regulares más allá del orden 3.
.png){kind=link}