¿Cuál es el ancho de ruta de la cuadrícula 3D (malla o enrejado) con longitud de longitud k?

Hice esta pregunta hace unas semanas en mathoverflow , pero no obtuve respuesta.

Aquí, por rejilla 3D de longitud de lado me refiero a la gráfica G = ( V , E ) con V = { 1 , ... , k } 3 y E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + | $k$$G=(V,E)$$V= \{1,\ldots,k\}^3$ , es decir, los nodos se colocan en coordenadas enteras tridimensionales entre 1 yk , y un nodo está conectado a los otros 6 nodos como máximo que difieren exactamente en una coordenada por uno.$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$$k$

¿Cuál es el nombre de este gráfico? Usaré la cuadrícula 3D, pero tal vez la malla 3D o la red 3D son a lo que otras personas están acostumbradas.

¿Cuál es el ancho de árbol o ancho de ruta de este gráfico? ¿Ya está publicado en alguna parte?

Ya sé que , es decir, es realmente más pequeño que k 2 . Para mí, esto sugiere que los argumentos estándar que muestran que la cuadrícula 2D k × k tiene ancho de árbol y ancho de ruta k no se generalizarán fácilmente.$tw(G) = (3/4) k^2 + O(k)$$k^2$$k\times k$$k$

Para ver esto, consideramos una descomposición de ruta que "barre" la cuadrícula utilizando principalmente conjuntos de nodos de la forma . Observar | S c | ≤ ( 3 / 4 ) k 2 + O ( k ) , S 3 / 2 k siendo el más grande tal conjunto. Los conjuntos entre S c y$S_c= \{(x,y,z)\mid x+y+z = c\}$$|S_c| \leq (3/4) k^2 + O(k)$$S_{3/2 k}$$S_c$ se crean barriendo con una línea y necesitan O ( k ) nodos adicionales para ser separadores. Más precisamente, use los conjuntos S c , d = { ( x , y , z ) ∣ ( x + y + z = c ∧ x ≤ d ) ∨ ( x + y + z = c ∧ x ≥ d ) $S_{c+1}$$O(k)$$S_{c,d} = \{(x,y,z)\mid (x+y+z = c \wedge x \leq d ) \vee (x+y+z = c \wedge x \geq d ) \}$como una descomposición camino de .$G$

También tengo una idea para una prueba que muestra , pero aún no está terminada.$tw(G) = \Omega(k^2)$

El ancho de ruta de puede determinarse como un corolario de algunos resultados conocidos. FitzGerald [2] mostró que el ancho de banda de P 3 k es ⌊ $P^3_k$$P^3_k$. Harper [3] mostró una condición tal que si un gráfico satisface la condición, entonces su ancho de ruta y ancho de banda son los mismos. Moghadam [4,5] y Bollobás y Leader [1] mostraron independientemente que cualquier grilla multidimensional satisface la condición de Harper. Estos resultados implican que el ancho de ruta deP 3 k también es⌊$\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$$P^3_k$.$\lfloor \frac{3}{4} k^{2} + \frac{1}{2}k \rfloor$

En nuestro artículo mencionado por Hsien-Chih, generalizamos el resultado de FitzGerald como explicó Yoshio. Creo que el ancho de árbol de no se conoce.$P^3_k$

FYI: Acabo de enviar una versión en inglés de nuestro artículo a arXiv.

1. B. Bollobás e I. Líder, Compresiones y desigualdades isoperimétricas, J. Combin. Teoría Ser. A 56 (1991) 47-62.
2. CH FitzGerald, Indización óptima de los vértices de los gráficos, Matemáticas. Comp. 28 (1974), 825-831.
3. LH Harper, Numeración óptima y problemas isoperimétricos en gráficos, J. Combin. Teoría 1 (1966) 385-393.
4. HS Moghadam, operadores de compresión y una solución al problema del ancho de banda del producto de caminos, Ph.D. Tesis, Universidad de California, Riverside (1983).$n$
5. HS Moghadam, Ancho de banda del producto de caminos, Congr. Numer. 173 (2005) 3-15.$n$

El ancho de ruta de las cuadrículas 3D ha sido estudiado por Ryohei Suda, Yota Otachi y Koichi Yamazaki en el documento Pathwidth of tridimensional grids , IEICE Tech. Informe, 2009.

Se afirma en el resumen del documento que

En este artículo, damos el ancho de ruta de las cuadrículas tridimensionales en forma cerrada, determinando el ancho del límite de su vértice.

Sin embargo, el límite preciso no se indica en el resumen, y actualmente no puedo acceder al documento completo. Tal vez pueda contactar a los autores en privado y publicar una respuesta a esta pregunta usted mismo, si los autores están dispuestos a compartir el resultado.