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

12

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 | + | CkG=(V,E)V={1,,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))|ax|+|by|+|cz|=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)k2+O(k)k2k×kk

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 ySc={(x,y,z)x+y+z=c}|Sc|(3/4)k2+O(k)S3/2kSc 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 ) }Sc+1O(k)Sc,d={(x,y,z)(x+y+z=cxd)(x+y+z=cxd)}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)=Ω(k2)

Riko Jacob
fuente
para c = k / 2 . ¿Me estoy perdiendo de algo? |Sc|=Ω(k2)c=k/2
Sariel Har-Peled
Seguro. Pero solo se usa en el límite superior. Lo que realmente me importa es un límite inferior. Sc
Riko Jacob el
Te puede interesar este artículo: springerlink.com/content/3nmjlc1g5emx9vpk . Si se puede calcular el "número de cola" de la gráfica, a continuación, se le dará un límite inferior en su camino de ancho usando el teorema 1 que establece que para cualquier gráfico G . qn(G)pw(G)G
Mathieu Chapelle
Oh. Veo. Significaste . (3/4)k2
Sariel Har-Peled
1
@Sariel: Edité la pregunta para evitar la misma confusión.
Tsuyoshi Ito

Respuestas:

13

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 3Pk3Pk3. 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 es334k2+12kPk3.34k2+12k

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.Pk3

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
Yota Otachi
fuente
Gracias por compartir amablemente su nuevo resultado (¡y papel!) Además, bienvenido a TCS SE :)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Me hiciste decidir compartir nuestro resultado :-) Gracias. De hecho, también soy nuevo en arXiv.
Yota Otachi
6

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.

Hsien-Chih Chang 張顯 之
fuente
Tenga en cuenta que el documento está escrito en japonés.
Tsuyoshi Ito
@ Tsuyoshi: Sí, es posible que necesitemos tu ayuda :)
Hsien-Chih Chang 張顯 之
44
P×Pm×Pnm+mn+2m(+mn12)2Pkkmn
pw(Pk3)=34k2+O(k)
Gracias. Parece que no tengo que sentirme mal por no encontrar esa referencia yo mismo. Tengo curiosidad por los detalles.
Riko Jacob