¿Cuántas por pares tocando "formas" son una red de $n\times n\times n$?

Question

Partición de un $n\times n\times n$ cuadrícula de cubos en las "formas", que son conjuntos de cubos conectados por las caras. ¿Cuál es el mayor número de formas que se pueden tocar todos los demás de la forma (tocar = compartir una cara)?

---

Aquí está una imagen de la $2$-dimensiones versión del problema, el cual es simple de resolver: para $n=1,2,3$ de las respuestas se $1,3$ $4$ respectivamente. Es de suponer que por $n\ge4$, la respuesta $4$ o tendríamos una gráfica que no es $4$-colourable.

Answer 1

Deje $f(n)$ ser el número máximo de pares de tocar las "formas" en un $n\times n\times n$ cuadrícula.

---

Tenemos $f(n)\ge n$, como se puede ver en la siguiente imagen de la Wikipedia en alemán, artículo en el "teorema de los Cuatro colores":

Para $n\ge 4$ podemos pila de dos de estas construcciones con completamente diferentes colores para encontrar $f(n)\ge 2n$. Esta podría ser la mejor manera posible, pero no sé. El resto de los casos son como sigue:

• $f(1)=1$, obviamente.
• $f(2)=4$, y este es el mejor posible.

Prueba.

Si hay más de cuatro formas se utilizan, a continuación, una de las figuras deben consta de un solo cubo. Este cubo debe ser lugares en una de las esquinas de la cuadrícula. Pero, a continuación, sólo hay tres caras restantes con los que se pueden tocar otras formas. Así que no hay quinto de la forma de tocar de este cubo.

• $f(3)\ge 5$, y no estoy seguro de si $6$ es posible. Pero yo no lo creo.

---

Por cierto, creo que tu pregunta se puede pedir en puramente gráfico términos teóricos:

El $n\times n\times n$ cuadrícula gráfico de $G$ está dado por $V(G)=\{1,...,n\}^3$ y $$E(G)=\left\{\{v,w\}\in {V\choose 2}\;\middle|\; |v-w|_1=1\right\}.$$ ¿Cuál es el mayor $k$, de modo que el grafo completo $K_k$ es menor de $G$?