En matemáticas , el permutoedro de orden n es un politopo ( n - 1) dimensional incrustado en un espacio n -dimensional. Sus coordenadas de vértice (etiquetas) son las permutaciones de los primeros n números naturales . Los bordes identifican los caminos más cortos posibles (conjuntos de transposiciones ) que conectan dos vértices (permutaciones). Dos permutaciones conectadas por un borde difieren solo en dos lugares (una transposición ), y los números en estos lugares son vecinos (difieren en valor en 1).
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/4/4f/Symmetric_group_4%3B_permutohedron_3D%3B_transpositions_%281-based%29.png/300px-Symmetric_group_4%3B_permutohedron_3D%3B_transpositions_%281-based%29.png)
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 borde corresponden a las 6 posibles transposiciones de 4 elementos, es decir, indican en qué dos lugares difieren las permutaciones conectadas. (Por ejemplo, los bordes rojos conectan permutaciones que difieren en los dos últimos lugares).
Historia
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 usa la ortografía alternativa permut a edron . [2] Los permutoedros a veces se denominan politopos de permutación , pero esta terminología también se utiliza para el politopo de Birkhoff relacionado , definido como el casco convexo 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.
Vértices, aristas y facetas
vértices , aristas , facetas , caras Dimensión de la cara d = n - k . |
k = 1 2 3 4 5 n 1 1 1 2 1 2 3 3 1 6 6 13 4 1 14 36 24 75 5 1 30 150 240 120 541 |
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 !/2y su longitud es √ 2 .
Dos vértices conectados difieren 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 al intercambiar 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 en S son más pequeñas que el resto . [4]
Ejemplos de facetas | ||||
---|---|---|---|---|
Para el orden 3, las facetas son las 6 aristas y para el orden 4 son las 14 caras . | ||||
orden 3 | orden 4 | |||
Subconjuntos de 1 elemento | Subconjuntos de 2 elementos | Subconjuntos de 1 elemento | Subconjuntos de 2 elementos | Subconjuntos de 3 elementos |
![]() | ![]() | ![]() | ![]() | ![]() |
Más en general, las caras de dimensiones 0 (vértices) a n - 1 (la permutohedron sí mismo) corresponden a los estrictos ordenamientos débiles del conjunto {1 ... n } . Entonces, 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 una ordenación con k = n - d clases de equivalencia.
Ejemplos de caras | |||||||
---|---|---|---|---|---|---|---|
orden 3 | orden 4 | ||||||
![]() | ![]() | ||||||
Las imágenes de arriba muestran las celosías faciales de los permutoedros de orden 3 y 4 (sin las caras vacías) . El vértice etiqueta a | b | c | d interpretadas como permutaciones (a, b, c, d) son las que forman el gráfico de Cayley.
|
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 que representan los números de Stirling del segundo tipo.
Se muestra a la derecha junto con las sumas de sus filas, los números de Bell ordenados .
Otras propiedades
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/6/69/Symmetric_group_4%3B_Cayley_graph_1%2C2%2C6_%281-based%29.png/300px-Symmetric_group_4%3B_Cayley_graph_1%2C2%2C6_%281-based%29.png)
El permutoedro tiene vértice-transitivo : el grupo simétrico S n actúa sobre el permutoedro por 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 los vectores básicos estándar . [6]
Los vértices y aristas del permutoedro son isomorfos a uno de los gráficos de Cayley del grupo simétrico , a saber, 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 . Sus colores de borde representan las 3 transposiciones generadoras: (1, 2) , (2, 3) , (3, 4)
Este gráfico de Cayley es hamiltoniano ; se puede encontrar un ciclo hamiltoniano mediante el algoritmo Steinhaus-Johnson-Trotter .
Teselado del espacio
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
- 1 + 2 + ... + n = n ( n + 1) / 2.
Además, este hiperplano puede ser embaldosado por un número infinito de 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 n -tuplas de enteros que suman cero y cuyos residuos (módulo n ) son todos iguales:
- x 1 + x 2 + ... + x n = 0
- x 1 ≡ x 2 ≡ ... ≡ x norte (mod norte ).
Esta es la celosía , la celosía dual de la celosía raíz A norte - 1 {\ Displaystyle A_ {n-1}} . En otras palabras, el permutoedro es la celda de Voronoi para. En consecuencia, esta celosía a veces se denomina celosía permutoédrica. [8]
Por lo tanto, el permutoedro de orden 4 que se muestra arriba divide 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,
- x + y + z + w = 10.
Uno comprueba fácilmente que para cada uno de los siguientes cuatro vectores,
- (1,1,1, −3), (1,1, −3,1), (1, −3,1,1) y (−3,1,1,1),
la suma de las coordenadas es cero y todas las coordenadas son congruentes con 1 (mod 4). Cualquiera de estos tres vectores genera 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.
Ejemplos de
Orden 2 | Orden 3 | Orden 4 | Orden 5 | Orden 6 |
---|---|---|---|---|
2 vértices | 6 vértices | 24 vértices | 120 vértices | 720 vértices |
![]() | ![]() | ![]() | ![]() | ![]() |
segmento de línea | hexágono | octaedro truncado | omnitruncado de 5 celdas | omnitruncado 5-simplex |
Ver también
- Associahedron
- Cicloedro
Notas
- ^ Original francés: "le mot permutoèdre est barbare, mais il est facile à retenir; soumettons-le aux critiques des lecteurs".
- ^ Thomas (2006) .
- ^ Gaiha y Gupta (1977) .
- ↑ Lancia (2018) , p. 105 (ver capítulo El Permutaedro ).
- ^ Véase, por ejemplo, Ziegler (1995) , p. 18.
- ^ Ziegler (1995) , p. 200.
- ^ Este etiquetado de gráfico de Cayley se muestra, por ejemplo, por Ziegler (1995) .
- ^ Baek, Adams y Dolson (2013) .
Referencias
- Baek, Jongmin; Adams, Andrew; Dolson, Jennifer (2013), "Filtrado gaussiano de alta dimensión basado en celosía y celosía permutoédrica", 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), "Poliedros de permutación", 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 derivados regularmente de los politopos regulares", Verhandelingen der Koninklijke Akademie van Wetenschappen Te Amsterdam , 11 (3): 87 págs. Googlebook, 370–381 También en línea en la Biblioteca digital KNAW en http://www.dwc.knaw.nl/toegangen/digital-library-knaw/?pagetype=publDetail&pId=PU00011495
- Thomas, Rekha R. (2006), "Capítulo 9. El permutaedro", Conferencias sobre combinatoria geométrica , Biblioteca de matemáticas para estudiantes: Subseries IAS / Park City Mathematical, 33 , American Mathematical Society , págs. 85–92, ISBN 978-0-8218-4140-2.
- Ziegler, Günter M. (1995), Conferencias sobre politopos , Springer-Verlag, Textos de posgrado en matemáticas 152.
Otras lecturas
- Le Conte de Poly-Barbut, Cl. (1990), "Le diagramme du treillis permutoèdre est intersection des diagrammes 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 (6): 1026–1106, arXiv : math.CO/0507163 , doi : 10.1093 / imrn / rnn153 , MR 2487491
- Santmyer, Joe (2007), "Para todas las distancias posibles, mire el permutoedro", Revista de matemáticas , 80 (2): 120–125, doi : 10.1080 / 0025570X.2007.11953465
enlaces externos
- Bryan Jacobs, "Permutohedron" , MathWorld