Encontrar la triangulación más pequeño de n-dimensional

Question

¿Cómo encontrar la triangulación más pequeño del cubo n-dimensional en n-simplices?

Se sabe, por ejemplo, que el cubo 4D (hypercube) puede ser dividido en 16 4-simplices, y esto es mínimo. Pero el número mínimo es desconocido a excepción de algunos pequeños valores de n que han cedido a búsquedas exhaustiva del ordenador.

(Estas etiquetas no están disponibles para mí: hypercube, búsqueda electrónica)

Answer 1

Esta es una difícil pregunta de investigación. Como achille hui dice, uno de los mejores cotas inferiores para el número de n-simplices conocido es de (aproximadamente) $2^n n! /n^{n/2}$, obtenido por Hadamard de la desigualdad, que le da un límite superior en el volumen que un simple contenida en el cubo puede tener. (achille parece estar olvidando de un factor de $2^n$, que surge del hecho de que Hadamard la desigualdad es acerca de la $[-1,1]^n$ cubo, en lugar de la $[0,1]$ cubo).

Este "Hadamard obligado" fue mejorado por Warren D. Smith mediante Hiperbolic volumen y, muy recientemente, por Alexey Glazyrin. Que cambiar el $2^n$ factor a, respectivamente, $6^{n/2}$ $e^n$ (http://www.sciencedirect.com/science/article/pii/S019566989990327X, http://arxiv.org/abs/0910.4200).

En términos de tiempo real de las construcciones de las triangulaciones con "pocos" simplices, el tamaño más pequeño de una triangulación es conocido sólo a la dimensión 7. Fue calculada por Anderson y Hughes (http://www.sciencedirect.com/science/article/pii/0012365X95000758) y se ha $1493$ simplices.

Para grandes dimensiones de los cubos, no es un "simple pero relativamente eficiente" truco por Haiman (http://link.springer.com/article/10.1007%2FBF02574690) que básicamente dice: Si se puede triangular $n$-cubo con $\alpha^n n!$ simplices de una cierta dimensión, luego por la adopción de los productos Cartesianos puede triangular cada $N$-cubo ($N$ es ahora considere muy grande) también con $\alpha^N N!$ simplices. El mejor valor de $\alpha$ conocido hasta el momento se obtiene el valor mínimo de la triangulación de la $7$-cubo, $1493 = 0.840^7 7!$. Es decir, Haiman el truco le da triangulaciones con $0.840^N N!$ simplices.

Con más argumento elaborado yo, con D. Orden, construido triangulaciones de la $N$-cubo con (asintóticamente), $0.816^N N!$ simplices (http://link.springer.com/article/10.1007%2Fs00454-003-2845-5, http://arxiv.org/abs/math.CO/0204157).

Para cubos de pequeña dimensión, aparte de la de Anderson-Hughes papel se mencionó anteriormente, quisiera citar este artículo de la Bienaventuranza y de la Ub, el trato con los límites inferiores: http://link.springer.com/article/10.1007%2Fs00454-004-1128-0, http://arxiv.org/abs/math/0310142

Resumiendo, yo diría que hasta el momento "sofisticado ideas" proporcionar sólo pequeñas mejoras a las "ideas simples" (por "simple", me refiero a Hadamard de los límites inferiores y Haiman explícita de construcciones / límites superior).

Answer 2

Deje $S(n)$ ser el número mínimo de simplices en la triangulación de un $n$-dimensiones del cubo. Parece que el siguiente.

Desde una $n$-dimensional del cubo ha $2^n$ vértices y un $n$-simplex ha $n+1$ vértices, podemos ver que $S(n)\ge 2^n/(n+1).$

Una triangulación de un $n$-dimensional del cubo induce una triangulación de cada una de las $(n-1)$-dimensiones de la cara de la $n$-cubo. Desde cada una cara tiene al menos $S(n-1)$ $(n-1)$-simplices, y cada una de las $n$-simplex ha $n+1$ $(n-1)$-dimensiones de las caras, tenemos que $S(n)\ge S(n-1)\cdot 2n/(n+1).$

Por otra parte, si se tiene en cuenta (1-dimensional) aristas en lugar de $(n-1)$dimensiones de las caras, se obtiene la envolvente como $S(n)\ge (2n(n-1)S(n-1)-2^n)/(n+1)$ (cada una de las $k$-simplex ha $k(k+1)/2$ bordes, cada una de las $(n-1)$-dimensiones de la cara de los rendimientos de $S(n-1)$ aristas y los bordes de la $n$-cubo se cuentan dos veces. Esta enlazada puede ser mejorado, porque cada arista de la triangulación de la $n$-cube que no es un borde de la $n$-cubo, pertenecen al menos a dos simplices de la triangulación. Entonces tenemos encuadernado $S(n)\ge (4n(n-1)S(n-1)-3\cdot 2^n)/(n+1).$

Por otra parte, la obligada $S(n)\ge S(n-1)\cdot 2n/(n+1)$ puede ser mejorado, ya que un $n$-dimensional del cubo ha $n$-pares de paralelas $(n-1)$dimensiones de las caras y cada simplex de la triangulación no tiene paralelo $(n-1)$dimensiones de las caras. Por lo que tiene un $(n-1)$-dimensiones de la cara, que no se encuentra en un $(n-1)$-dimensiones de la cara del cubo. Por lo tanto, tenemos enlazado $S(n)\ge 2S(n-1)$.