El número de circuitos de Hamilton en un politopo convexo incrustado en $\mathbb{R}^N$

Question

Recientemente me pregunté si podría haber una medida natural de complejidad topológica para poliedros convexos incrustados en $\mathbb{R}^N$. Después de reflexionar, se me ocurrió que el número de ciclos hamiltonianos distintos en un poliedro convexo podría ser una medida de proximidad útil. Ahora, supongamos que la fórmula asintótica para el número máximo de ciclos hamiltonianos en un poliedro convexo de $n$ vértices incrustado en $\mathbb{R}^N$ está dada por:

\begin{equation} f_N(n) \tag{1} \end{equation}

Lo que me intriga es si existe un polinomio $P(n)$ tal que:

\begin{equation} \forall N \in \mathbb{N},\frac{f_{N+1}(n)}{f_{N}(n)} \leq P(n) \tag{2} \end{equation}

Para ser concretos, en el caso de $(N=2,n=4)$ tenemos un cuadrado con 8 ciclos H y en el caso de $(N=3,n=4)$ tenemos un tetraedro con 24 ciclos H.

Nota: Después de hacer varias búsquedas en Google, aún no sé si este problema ya ha sido resuelto.

Answer 1

Para $N\ge 4$ y arbitrario $n\ge N+1$ hay un politopo con grafo de aristas $K_n$, por lo tanto $f_N(n)=n!$. Entonces si $n\ge N+2$ entonces

$$\frac{f_{N+1}(n)}{f_N(n)} = 1.$$

También se debe tener en cuenta que $f_N(n)$ no está bien definido para $n\le N$. Por lo tanto, hablar de arbitrariamente grande $N$ para un $n$ fijo podría ser problemático.