Qual é a largura do caminho da grade 3D (malha ou treliça) com o comprimento da linha k?

Fiz essa pergunta há algumas semanas no mathoverflow , mas não obtive resposta.

Aqui, por grade 3D de comprimento lateral , refiro-me ao gráfico com e , ou seja, os nós são colocados em coordenadas inteiras tridimensionais entre 1 e , e um nó é conectado ao at mais 6 outros nós que diferem precisamente em uma coordenada por uma.G = ( V , E ) V = { 1 , … , k } 3 E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + | c - z | = 1 } $k$$G=(V,E)$$V= \{1,\ldots,k\}^3$$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$$k$

Qual é o nome deste gráfico? Usarei a grade 3D, mas talvez a malha 3D ou a treliça 3D sejam o que outras pessoas estão acostumadas.

Qual é a largura da árvore ou caminho deste gráfico? Isso já está publicado em algum lugar?

Eu já sei que , ou seja, é realmente menor que . Para mim, isso sugere que os argumentos padrão que mostram que a grade 2D tem largura de árvore e largura de caminho não serão facilmente generalizados.k 2 k x k $tw(G) = (3/4) k^2 + O(k)$$k^2$$k\times k$$k$

Para ver isso, consideramos uma decomposição de caminho que "varre" a grade usando principalmente conjuntos de nós no formato . Observe , sendo o maior conjunto desse tipo. Os conjuntos entre e são criados varrendo com uma linha e precisam de nós adicionais para serem separadores. Mais precisamente, use os conjuntos como um caminho de decomposição .| S c | ≤ ( 3 / 4 ) K 2 + S ( k ) S 3 / 2 K S c S c + 1 O ( k ) S c , d = { ( x $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$$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 ) \}$$G$

Eu também tenho uma idéia para uma prova que mostre , mas isso ainda não foi concluído.$tw(G) = \Omega(k^2)$

A largura do caminho de pode ser determinada como um corolário de alguns resultados conhecidos. FitzGerald [2] mostrou que a largura de banda de P 3 k é ⌊ $P^3_k$$P^3_k$. Harper [3] mostrou uma condição tal que, se um gráfico satisfaz a condição, sua largura de banda e largura de banda são as mesmas. Moghadam [4,5] e Bollobás e Leader [1] mostraram independentemente que qualquer grade multidimensional satisfaz a condição de Harper. Esses resultados sugerem que a largura do caminho deP 3 k também é⌊$\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$

Em nosso artigo mencionado por Hsien-Chih, generalizamos o resultado de FitzGerald como Yoshio explicou. Eu acredito que a largura de árvore de não é conhecida.$P^3_k$

FYI: Acabei de enviar uma versão em inglês do nosso artigo para o arXiv.

1. B. Bollobás e I. Leader, Compressões e desigualdades isoperimétricas, J. Combin. Teoria Ser. A 56 (1991) 47-62.
2. CH FitzGerald, indexação ideal dos vértices dos gráficos, matemática. Comp. 28 (1974), 825-831.
3. LH Harper, numerações ótimas e problemas isoperimétricos em gráficos, J. Combin. Teoria 1 (1966) 385-393.
4. HS Moghadam, operadores de compressão e uma solução para o problema de largura de banda do produto de caminhos, Ph.D. tese, Universidade da Califórnia, Riverside (1983).$n$
5. HS Moghadam, Largura de banda do produto de caminhos, Congr. Numer. 173 (2005) 3-15.$n$

A largura de caminho das grades 3D foi estudada por Ryohei Suda, Yota Otachi e Koichi Yamazaki no artigo Largura de caminho de grades tridimensionais , IEICE Tech. Relatório, 2009.

Alega-se no resumo do artigo que

Neste artigo, apresentamos a largura de caminho de grades tridimensionais em forma fechada, determinando sua largura de limite de vértice.

No entanto, o limite preciso não é indicado no resumo e, atualmente, não consigo acessar o artigo completo. Talvez você possa entrar em contato com os autores em particular e postar uma resposta a esta pergunta sozinho, se os autores estiverem dispostos a compartilhar o resultado.