Permutoedro

En matemáticas , el permutoedro (también escrito permutahedron ) 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 . Dos permutaciones conectadas por una arista difieren en solo dos posiciones (una transposición ), y los números en estas posiciones 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. Los 6 colores de las aristas corresponden a las 6 posibles transposiciones de 4 elementos, es decir, indican en qué dos posiciones difieren las permutaciones conectadas. (Por ejemplo, las aristas rojas conectan permutaciones que difieren en las dos últimas posiciones).

Según Günter M. Ziegler ( 1995 ) , los permutohedra 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 ]}   

También se utiliza a veces la grafía alternativa permut a hedron . ^{[ 2 ]} A los permutohedros se les llama a veces politopos de permutación , pero esta terminología también se usa 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 ) usa 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 otros n − 1. El número de aristas es ⁠ ( n − 1) n ! / 2 ⁠ , y su longitud es √ 2 .

Dos vértices conectados por una arista difieren en un intercambio de dos coordenadas cuyos valores difieren en 1. ^{[ 3 ]} El par de posiciones intercambiadas 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 difieren en el intercambio de 2 y 3 en las dos primeras posiciones. Los valores 2 y 3 difieren en 1. Todas las aristas azules corresponden a intercambios de coordenadas en las dos primeras posiciones).

El número de facetas es 2 ⁿ − 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 órdenes 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 orden 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 ) : $${\displaystyle T(n,k)=k!\cdot \left\{{n \atop k}\right\}}$$ con${\displaystyle \textstyle \left\{{n \atop k}\right\}}$representando los números de Stirling de segunda especie .

Se muestra a la derecha junto con las sumas de sus filas, los números de Bell ordenados .

El permutoedro es transitivo en los vértices : el grupo simétrico S _n actúa sobre el permutoedro mediante la permutación de coordenadas.

El permutoedro es un zonotopo ; una copia trasladada del permutoedro se puede generar como la suma de Minkowski de los n ( n − 1)/2 segmentos de línea que conectan los pares de los vectores base estándar . ^{[ 6 ]}

El grafo de vértices y aristas del permutoedro es el grafo de Bruhat , que es un grafo de Cayley del grupo simétrico generado por las transposiciones que intercambian elementos consecutivos. Los vértices del grafo de Cayley son las permutaciones inversas de los 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 grafo de Cayley es hamiltoniano ; se puede encontrar un ciclo hamiltoniano mediante el algoritmo de Steinhaus-Johnson-Trotter .

Teselación del espacio mediante permutohedros de órdenes 3 y 4.

El permutoedro de orden n se encuentra completamente en el hiperplano ( n − 1) dimensional que consta de todos los puntos cuyas coordenadas suman el número:

$${\displaystyle 1+2+\ldots +n={\frac {n(n+1)}{2}}}$$

Además, este hiperplano puede ser recubierto por infinitas copias trasladadas del permutoedro. Cada una de ellas difiere del permutoedro básico por un elemento de una cierta red ( n − 1) dimensional , que consiste en las n -tuplas de enteros que suman cero y cuyos residuos (módulo n ) son todos iguales: $${\displaystyle {\begin{aligned}&x_{1}+x_{2}+\ldots +x_{n}=0\\&x_{1}\equiv x_{2}\equiv \ldots \equiv x_{n}{\pmod {n}}.\end{aligned}}}$$

Esta es la red${\displaystyle A_{n-1}^{*}}$, la red dual de la red raíz${\displaystyle A_{n-1}}$En otras palabras, el permutoedro es la celda de Voronoi para${\displaystyle A_{n-1}^{*}}$. En consecuencia, esta red a veces se denomina red permutoédrica. ^{[ 8 ]}

Así, el permutoedro de orden 4 mostrado arriba recubre el espacio tridimensional mediante traslación. Aquí, el espacio tridimensional es el subespacio afín del espacio tetradimensional .${\displaystyle \mathbb {R} ^{4}}$con coordenadas x , y , z , w que consiste en las cuádruplas de números reales cuya suma es 10,

$${\displaystyle x+y+z+w=10.}$$

Se puede comprobar fácilmente que para cada uno de los siguientes cuatro vectores,

$${\displaystyle (1,1,1,-3),\ (1,1,-3,1),\ (1,-3,1,1),\ (-3,1,1,1),}$$

La suma de las coordenadas es cero y todas las coordenadas son congruentes con 1 (módulo 4). Cualquier combinación de tres de estos vectores genera la red de traslación.

Las teselaciones formadas de esta manera a partir de los permutohedros de orden 2, orden 3 y orden 4, respectivamente, son el apeirogon , el teselado 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.

• Asociaedro
• Cicloedro
• Permutoasociaedro

• Baek, Jongmin; Adams, Andrew; Dolson, Jennifer (2013), "Filtrado gaussiano de alta dimensión basado en retículos y el retículo permutoédrico", Journal of Mathematical Imaging and Vision , 46 (2): 211–237 , doi : 10.1007/s10851-012-0379-2 , hdl : 1721.1/105344 , MR 3061550 
• Bowman, V. Joseph (1972), "Permutation polyhedra", SIAM Journal on Applied Mathematics , 22 (4): 580– 589, doi : 10.1137/0122054 , JSTOR 2099695 , MR 0305800  .
• Gaiha, Prabha; Gupta, SK (1977), "Vértices adyacentes en un permutoedro", SIAM Journal on Applied Mathematics , 32 (2): 323–327 , doi : 10.1137/0132025 , JSTOR 2100417 , MR 0427102  .
• Guilbaud, Georges Th.; Rosenstiehl, Pierre (1963), "Analyse algébrique d'un scrutin" , Mathématiques et Sciences Humaines , 4 : 9– 33.
• Lancia, Giuseppe (2018), Modelos compactos de programación lineal extendida , Cham, Suiza: Springer, ISBN 978-3-319-63975-8.
• Schoute, Pieter Hendrik (1911), "Tratamiento analítico de los politopos regularmente derivados de los politopos regulares", Verhandelingen der Koninklijke Akademie van Wetenschappen te Amsterdam , 11 (3): 87 págs.Googlebook, 370–381 También disponible en línea en la Biblioteca Digital de la KNAW en http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
• Thomas, Rekha R. (2006), "Capítulo 9. El permutaedro", Lecciones de combinatoria geométrica , Biblioteca matemática estudiantil: Subserie matemática IAS/Park City, vol.  33, Sociedad Matemática Americana , pp. 85–92 , ISBN  978-0-8218-4140-2.
• Ziegler, Günter M. (1995), Lecciones sobre politopos , Springer-Verlag, Textos de posgrado en matemáticas 152.

• Huebschmann, J. (2012), "Trenzas y módulos cruzados", Journal of Group Theory , 15 : 57–83 , arXiv : 0904.3895 , doi : 10.1515/JGT.2011.095
• Le Conte de Poly-Barbut, cl. (1990), "Le diagramame du treillis permutoèdre est junction des diagramames de deux produits directs d'ordres totaux", Mathématiques, Informatique et Sciences Humaines , 112 : 49– 53.
• Postnikov, Alexander (2009), "Permutohedra, associahedra, and beyond", International Mathematics Research Notices , 2009 (6): 1026–1106 , arXiv : math.CO/0507163 , doi : 10.1093/imrn/rnn153 , MR 2487491 
• Santmyer, Joe (2007), "Para todas las distancias posibles, recurra al permutoedro", Mathematics Magazine , 80 (2): 120–125 , doi : 10.1080/0025570X.2007.11953465