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

12

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 } kkG=(V,E)V={1,,k}3E={((a,b,c),(x,y,z))|ax|+|by|+|cz|=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 ktw(G)=(3/4)k2+O(k)k2k×kk

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

Eu também tenho uma idéia para uma prova que mostre , mas isso ainda não foi concluído.tw(G)=Ω(k2)

Riko Jacob
fonte
para c = k / 2 . Estou esquecendo de algo? |Sc|=Ω(k2)c=k/2
Sariel Har-Peled
Certo. Mas é usado apenas no limite superior. O que realmente me importa é um limite inferior. Sc
precisa saber é o seguinte
Você pode estar interessado neste documento: springerlink.com/content/3nmjlc1g5emx9vpk . Se você pode calcular o "número da fila" de seu gráfico, então você vai ser dado um limite inferior no seu caminho de largura usando Teorema 1 que afirma que para qualquer gráfico G . qn(G)pw(G)G
Mathieu Chapelle
Oh Entendo. Está significava . (3/4)k2
Sariel Har-Peled
1
@ Sariel: Eu editei a pergunta para evitar a mesma confusão.
Tsuyoshi Ito

Respostas:

13

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

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

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
Yota Otachi
fonte
Obrigado por gentilmente partilha o seu novo resultado também, bem-vindo ao TCS SE :) (e papel!)
Hsien-Chih Chang張顯之
@ Hsien-Chih: Você me fez decidir compartilhar nosso resultado :-) Obrigado. De fato, também sou novo no arXiv.
Yota Otachi
6

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.

Hsien-Chih Chang 張顯 之
fonte
Observe que o artigo está escrito em japonês.
Tsuyoshi Ito
@Tsuyoshi: Sim, nós podemos precisar da sua ajuda :)
Hsien-Chih Chang張顯之
4
P×Pm×Pnm+mn+2m(+mn12)2Pkkmn
pw(Pk3)=34k2+O(k)
Obrigado. Parece que não preciso me sentir mal por não encontrar essa referência. Estou curioso pelos detalhes.
Riko Jacob