Berapa pathwidth dari 3D-grid (mesh atau lattice) dengan sidelength k?

Saya menanyakan pertanyaan ini beberapa minggu yang lalu di mathoverflow , tetapi saya tidak mendapat jawaban.

Di sini, dengan 3D-grid sidelength maksud saya grafik G = ( V , E ) dengan V = { 1 , ... , k } 3 dan E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + | $k$$G=(V,E)$$V= \{1,\ldots,k\}^3$ , yaitu, node ditempatkan pada koordinat integer 3 dimensi antara 1 dan k , dan sebuah node terhubung ke paling banyak 6 node lain yang berbeda dalam satu koordinat dengan satu.$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$$k$

Apa nama grafik ini? Saya akan menggunakan kisi 3D, tetapi mungkin kisi 3D atau kisi 3D adalah yang biasa digunakan orang lain.

Berapa treewidth atau pathwidth dari grafik ini? Apakah ini sudah diterbitkan di suatu tempat?

Aku sudah tahu bahwa , yaitu itu benar-benar lebih kecil dari k 2 . Bagi saya, ini menunjukkan bahwa argumen standar menunjukkan bahwa k × k 2D-grid memiliki treewidth dan pathwidth k tidak akan mudah digeneralisasi.$tw(G) = (3/4) k^2 + O(k)$$k^2$$k\times k$$k$

Untuk melihat ini, kami mempertimbangkan dekomposisi jalur yang "menyapu" grid menggunakan set simpul terutama dari bentuk . Amati | S c | ≤ ( 3 / 4 ) k 2 + O ( k ) , S 3 / 2 k menjadi set tersebut terbesar. Set antara S c dan$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$ dibuat dengan menyapu dengan garis dan membutuhkan O ( k ) simpul tambahan untuk menjadi pemisah. Lebih tepatnya, gunakan set 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 ) \}$sebagai dekomposisi jalur .$G$

Saya juga punya ide untuk bukti yang menunjukkan , tetapi itu belum selesai.$tw(G) = \Omega(k^2)$

The pathwidth dari dapat ditentukan sebagai konsekuensi untuk beberapa hasil dikenal. FitzGerald [2] menunjukkan bahwa bandwidth P 3 k adalah ⌊ $P^3_k$$P^3_k$. Harper [3] menunjukkan suatu kondisi sedemikian rupa sehingga jika sebuah grafik memenuhi kondisi tersebut, maka jalurnya dan bandwidthnya sama. Moghadam [4,5] dan Bollobás and Leader [1] secara independen menunjukkan bahwa setiap grid multi-dimensi memenuhi kondisi Harper. Hasil ini menyiratkan bahwa lebar jalurP 3 k juga⌊$\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$

Dalam makalah kami yang disebutkan oleh Hsien-Chih, kami menggeneralisasi hasil FitzGerald seperti yang dijelaskan Yoshio. Saya percaya treewidth dari tidak diketahui.$P^3_k$

FYI: Saya baru saja mengirimkan versi bahasa Inggris dari makalah kami ke arXiv.

1. B. Bollobás dan I. Pemimpin, Kompresi dan ketidaksetaraan isoperimetrik, J. Combin. Teori Ser. A 56 (1991) 47-62.
2. CH FitzGerald, Pengindeksan optimal dari simpul grafik, Matematika. Comp. 28 (1974), 825-831.
3. LH Harper, penomoran yang optimal dan masalah isoperimetri pada grafik, J. Combin. Teori 1 (1966) 385-393.
4. HS Moghadam, operator Kompresi dan solusi untuk masalah bandwidth dari produk paths, Ph.D. tesis, Universitas California, Riverside (1983).$n$
5. HS Moghadam, Bandwidth dari produk paths, Congr. Angka 173 (2005) 3-15.$n$

Pathwidth dari 3D-grid telah dipelajari oleh Ryohei Suda, Yota Otachi dan Koichi Yamazaki dalam paper Pathwidth dari grid 3-dimensi , IEICE Tech. Laporan, 2009.

Diklaim dalam abstrak makalah itu

Dalam makalah ini, kami memberikan pathwidth dari grid 3-dimensi dalam bentuk tertutup, dengan menentukan lebar batas verteks mereka.

Namun batas yang tepat tidak dinyatakan dalam abstrak, dan saat ini saya tidak dapat mengakses kertas lengkap. Mungkin Anda dapat menghubungi penulis secara pribadi, dan memposting jawaban untuk pertanyaan ini sendiri, jika penulis bersedia membagikan hasilnya.