Quelle est la largeur de chemin de la grille 3D (maillage ou treillis) de longueur latérale k?

J'ai posé cette question il y a quelques semaines à mathoverflow , mais je n'ai reçu aucune réponse.

Ici, par grille 3D de longueur latérale je veux dire le graphique avec et , c'est-à-dire que les nœuds sont placés à des coordonnées entières en 3 dimensions entre 1 et , et un nœud est connecté à l'at la plupart des 6 autres nœuds qui diffèrent précisément d'une coordonnée par une. $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$

Quel est le nom de ce graphique? J'utiliserai une grille 3D, mais peut-être que le maillage 3D ou le réseau 3D sont ce à quoi les autres sont habitués.

Quelle est la largeur d'arbre ou la largeur de chemin de ce graphique? Est-ce déjà publié quelque part?

Je sais déjà que , c'est-à-dire qu'il est vraiment plus petit que . Pour moi, cela suggère que les arguments standard montrant que la grille 2D a une largeur d'arbre et une largeur de chemin ne se généraliseront pas facilement. $tw(G) = (3/4) k^2 + O(k)$ $k^2$ $k\times k$ $k$

Pour voir cela, nous considérons une décomposition de chemin qui "balaye" la grille en utilisant principalement des ensembles de nœuds de la forme . Observer , étant le plus grand de ces ensembles. Les ensembles entre et sont créés en balayant avec une ligne et nécessitent nœuds supplémentaires pour être des séparateurs. Plus précisément, utilisez les ensembles en tant que décomposition de chemin de . $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$

J'ai aussi une idée pour une preuve qui montre , mais ce n'est pas encore fini. $tw(G) = \Omega(k^2)$

reference-request graph-theory co.combinatorics treewidth integer-lattice Riko Jacob
la source

pour

. Suis-je en train de manquer quelque chose?

| S_{c} | = Ω (k^{2})

$|S_c| = \Omega(k^2)$

c = ⌊ k / 2 ⌋

$c=\lfloor k/2 \rfloor$

Sariel Har-Peled

Sûr. Mais

n'est utilisé que dans la limite supérieure. Ce qui m'importe vraiment, c'est une limite inférieure.

S_{c}

$S_c$

Riko Jacob

Vous pouvez être intéressé par cet article: springerlink.com/content/3nmjlc1g5emx9vpk . Si vous pouvez calculer le « numéro de file d' attente » de votre graphique, vous recevrez un minorant sur son chemin largeur à l' aide Théorème 1 qui stipule que

pour tout graphe

q n (G) \leq p w (G)

$\mathsf{qn}(G) \leq \mathsf{pw}(G)$

G

$G$

Mathieu Chapelle

Oh. Je vois. Vous vouliez dire

(3 / 4) k^{2}

$(3/4)k^2$

Sariel Har-Peled

@Sariel: J'ai édité la question pour éviter la même confusion.

Tsuyoshi Ito

Réponses:

La largeur de trajet de peut être déterminée comme corollaire à certains résultats connus. FitzGerald [2] a montré que la bande passante de est $P^3_k$ $P^3_k$ . Harper [3] a montré une condition telle que si un graphe satisfait la condition, alors sa largeur de chemin et sa largeur de bande sont les mêmes. Moghadam [4,5] et Bollobás et Leader [1] ont montré indépendamment que toute grille multidimensionnelle satisfait la condition de Harper. Ces résultats impliquent que la largeur de chemin de est également $\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$

Dans notre article mentionné par Hsien-Chih, nous avons généralisé le résultat de FitzGerald comme Yoshio l'a expliqué. Je crois que la largeur d'arbre de n'est pas connue. $P^3_k$

FYI: Je viens de soumettre une version anglaise de notre article à arXiv.

B. Bollobás et I. Leader, Compressions et inégalités isopérimétriques, J. Combin. Theory Ser. A 56 (1991) 47-62.
CH FitzGerald, Indexation optimale des sommets des graphes, Math. Comp. 28 (1974), 825-831.
LH Harper, Numérotation optimale et problèmes isopérimétriques sur les graphiques, J. Combin. Théorie 1 (1966) 385-393.
HS Moghadam, Les opérateurs de compression et une solution au problème de bande passante du produit de chemins, Ph.D. thèse, Université de Californie, Riverside (1983). $n$
$n$

Yota Otachi
la source

Merci d'avoir bien voulu partager votre nouveau résultat (et votre papier!). Bienvenue également à TCS SE :)

Hsien-Chih Chang 之之

@ Hsien-Chih: Tu m'as fait décider de partager notre résultat :-) Merci. En fait, je suis aussi nouveau pour arXiv.

Yota Otachi

La largeur de chemin des grilles 3D a été étudiée par Ryohei Suda, Yota Otachi et Koichi Yamazaki dans l'article Pathwidth of 3-dimensional grids , IEICE Tech. Rapport, 2009.

Il est affirmé dans l’abrégé du document que

Dans cet article, nous donnons la largeur de chemin des grilles tridimensionnelles sous forme fermée, en déterminant leur largeur limite de sommet.

Cependant, la limite précise n'est pas indiquée dans le résumé, et actuellement je ne peux pas accéder au document complet. Vous pouvez peut-être contacter les auteurs en privé et publier une réponse à cette question par vous-même, si les auteurs souhaitent partager le résultat.

Hsien-Chih Chang 張顯之
la source

Notez que le document est écrit en japonais.

Tsuyoshi Ito

@Tsuyoshi: Oui, nous pourrions avoir besoin de votre aide :)

Hsien-Chih Chang 張顯之

P_{ℓ} \times P_{m} \times P_{n}

$P_{\ell}\times P_{m}\times P_{n}$

ℓ m

$\ell m$

ℓ + m \leq n + 2

$\ell + m \leq n + 2$

ℓ m - ⌈ (\frac{ℓ + m - n - 1}{2})^{2} ⌉

$\ell m - \lceil (\frac{\ell+m-n-1}{2})^2 \rceil$

P_{k}

$P_k$

k

$k$

ℓ \leq m \leq n

$\ell \leq m \leq n$

p w (P_{k}^{3}) = \frac{3}{4} k^{2} + O (k)

$\mathsf{pw}(P^3_k) = \frac{3}{4}k^2 + O(k)$

Merci. On dirait que je n'ai pas à me sentir mal de ne pas avoir trouvé cette référence moi-même. Je suis curieux des détails.

Riko Jacob