permutoedro
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 en solo 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 borde corresponden a las 6 transposiciones posibles 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).
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 ). Califican la palabra de 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 un edro . [2] Los permutoedros a veces se denominan politopos de permutación , pero esta terminología también se usa para el politopo de Birkhoff relacionado , definido como el casco convexo de las matrices de permutación . Más generalmente, 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 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).
.png){kind=spacer}
.png)
