Hipersimplex

En combinatoria poliédrica , el hipersímplex es un politopo convexo que generaliza el símplex . Está determinado por dos números enteros y , y se define como la envoltura convexa de los vectores -dimensionales cuyos coeficientes consisten en unos y ceros. De manera equivalente, se puede obtener cortando el hipercubo unitario -dimensional con el hiperplano de ecuación y, por esta razón, es un politopo -dimensional cuando . ^[1] ${\displaystyle \Delta _{d,k}}$ ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle d-k}$ ${\displaystyle \Delta _{d,k}}$ ${\displaystyle d}$ ${\displaystyle [0,1]^{d}}$ ${\displaystyle x_{1}+\cdots +x_{d}=k}$ ${\displaystyle (d-1)}$ ${\displaystyle 0<k<d}$

Propiedades

El número de vértices de es . ^[1] El gráfico formado por los vértices y las aristas del hipersímplex es el gráfico de Johnson . ^[2] ${\displaystyle \Delta _{d,k}}$ ${\displaystyle {\tbinom {d}{k}}}$ ${\displaystyle \Delta _{d,k}}$ ${\displaystyle J(d,k)}$

Construcciones alternativas

Una construcción alternativa (para ) es tomar la envoltura convexa de todos los vectores -dimensionales que tienen coordenadas nulas o no nulas. Esto tiene la ventaja de operar en un espacio que tiene la misma dimensión que el politopo resultante, pero la desventaja de que el politopo que produce es menos simétrico (aunque combinatoriamente equivalente al resultado de la otra construcción). ${\displaystyle 0<k<d}$ ${\displaystyle (d-1)}$ ${\displaystyle (0,1)}$ ${\displaystyle k-1}$ ${\displaystyle k}$

El hipersímplex es también el politopo matroide para un matroide uniforme con elementos y rango . ^[3] ${\displaystyle \Delta _{d,k}}$ ${\displaystyle d}$ ${\displaystyle k}$

Ejemplos

El hipersímplex es un -símplex (y por lo tanto, tiene vértices). El hipersímplex es un octaedro y el hipersímplex es un 5-cell rectificado . ${\displaystyle \Delta _{d,1}}$ ${\displaystyle (d-1)}$ ${\displaystyle d}$ ${\displaystyle \Delta _{4,2}}$ ${\displaystyle \Delta _{5,2}}$

Generalmente , el hipersímplex, , corresponde a un politopo uniforme , siendo el símplex -dimensional rectificado , con vértices posicionados en el centro de todas las caras -dimensionales de un símplex -dimensional. ${\displaystyle \Delta _{d,k}}$ ${\displaystyle (k-1)}$ ${\displaystyle (d-1)}$ ${\displaystyle (k-1)}$ ${\displaystyle (d-1)}$

Historia

Los hipersímplices fueron estudiados y nombrados por primera vez en el cálculo de clases características (un tema importante en topología algebraica ), por Gabrièlov, Gelʹfand y Losik (1975). ^{[4] [5]}

Referencias

1. Miller, Ezra; Reiner, Victor; Sturmfels, Bernd , Combinatoria geométrica, serie de matemáticas IAS/Park City, vol. 13, American Mathematical Society, pág. 655, ISBN 9780821886953.
2. Rispoli, Fred J. (2008), El gráfico del hipersímplex , arXiv : 0811.2981 , Bibcode :2008arXiv0811.2981R.
3. Grötschel, Martin (2004), "Sistemas de conjuntos homogéneos de cardinalidad, ciclos en matroides y politopos asociados", The Sharpest Cut: The Impact of Manfred Padberg and His Work , MPS/SIAM Ser. Optim., SIAM, Filadelfia, PA, págs. 99-120, MR  2077557. Véanse en particular las observaciones que siguen a la Proposición 8.20 en la pág. 114.
4. Gabrièlov, AM; Gelʹfand, IM ; Losik, MV (1975), "Cálculo combinatorio de clases características. I, II", Akademija Nauk SSSR , 9 (2): 12–28, ibid. 9 (1975), no. 3, 5–26, MR  0410758.
5. Ziegler, Günter M. (1995), Lecciones sobre politopos , Textos de posgrado en matemáticas, vol. 152, Springer-Verlag, Nueva York, pág. 20, doi :10.1007/978-1-4613-8431-1, ISBN 0-387-94365-X, Sr.  1311028.

Lectura adicional

• Hibi, Takayuki; Solus, Liam (2016), "Facetas del (n , k) -hipersímplex r -estable ", Annals of Combinatorics , 20 : 815–829, arXiv : 1408.5932 , Bibcode :2014arXiv1408.5932H, doi : 10.1007/s00026-016-0325-x.