Jaka jest szerokość ścieżki siatki 3D (siatki lub kraty) o długości bocznej k?

Zadałem to pytanie kilka tygodni temu w Mathoverflow , ale nie otrzymałem odpowiedzi.

Tutaj przez siatkę 3D długości bocznej rozumiem wykres G = ( V , E ) z V = { 1 , … , k } 3 i E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + | $k$$G=(V,E)$$V= \{1,\ldots,k\}^3$ , tzn. Węzły są umieszczone na trójwymiarowych współrzędnych całkowitych od 1 do k , a węzeł jest podłączony do co najwyżej 6 innych węzłów, które różnią się dokładnie jedną współrzędną o jeden.$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$$k$

Jak nazywa się ten wykres? Użyję siatki 3D, ale być może siatka 3D lub sieć 3D są tym, do czego przywykli inni ludzie.

Jaka jest szerokość lub szerokość tego wykresu? Czy to już gdzieś opublikowano?

Wiem już, że , czyli jest mniejszy niż naprawdę k 2 . Według mnie sugeruje to, że standardowe argumenty pokazujące, że siatka 2D k × k ma szerokość i szerokość ścieżki k , nie będą łatwe do uogólnienia.$tw(G) = (3/4) k^2 + O(k)$$k^2$$k\times k$$k$

Aby to zobaczyć, rozważamy rozkład ścieżki, który „zamiata” siatkę przy użyciu głównie zestawów węzłów w postaci . Obserwować | S c | ≤ ( 3 / 4 ) k 2 + O ( K ) , S 3 / 2 K jest największym taki zestaw. Zbiory między S c a$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ą tworzone przez zamiatanie za pomocą linii i potrzebują O ( k ) dodatkowych węzłów, które będą separatorami. Dokładniej, użyj zbiorów 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 ) \}$jako rozkładu po torze .$G$

Mam też pomysł na dowód, który pokazuje , ale jeszcze nie jest skończony.$tw(G) = \Omega(k^2)$

Ścieżkę można określić jako następstwo niektórych znanych wyników. FitzGerald [2] wykazał, że szerokość pasma P 3 k wynosi ⌊ $P^3_k$$P^3_k$. Harper [3] pokazał taki stan, że jeśli wykres spełnia ten warunek, to jego szerokość i szerokość pasma są takie same. Moghadam [4,5] oraz Bollobás i Leader [1] niezależnie wykazali, że każda wielowymiarowa siatka spełnia warunki Harpera. Wyniki te sugerują, że szerokość ścieżkiP 3 k również wynosi⌊$\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$

W naszym artykule wspomnianym przez Hsien-Chiha uogólniliśmy wynik FitzGerald, jak wyjaśnił Yoshio. Wierzę, że szerokość nie jest znana.$P^3_k$

FYI: Właśnie przesłałem angielską wersję naszego artykułu do arXiv.

1. B. Bollobás i I. Lider, Kompresje i nierówności izoperymetryczne, J. Combin. Teoria Ser. A 56 (1991) 47–62.
2. CH FitzGerald, Optymalne indeksowanie wierzchołków wykresów, Matematyka. Komp. 28 (1974) 825–831.
3. LH Harper, optymalne numeracje i problemy izoperymetryczne na wykresach, J. Combin. Teoria 1 (1966) 385-393.
4. HS Moghadam, operatory kompresji i rozwiązanie problemu przepustowości iloczynu ścieżek praca doktorska, University of California, Riverside (1983).$n$
5. HS Moghadam, Przepustowość iloczynu ścieżek, Congr. Liczba 173 (2005) 3-15.$n$

Ryohei Suda, Yota Otachi i Koichi Yamazaki badali przepustowość siatek 3D w artykule Pathwidth of trójwymiarowych siatek , IEICE Tech. Raport, 2009.

Twierdzi się w streszczeniu artykułu, że

W tym artykule podajemy szerokość ścieżek 3-wymiarowych siatek w formie zamkniętej, określając ich szerokość graniczną wierzchołków.

Jednak dokładna granica nie jest podana w streszczeniu, a obecnie nie mam dostępu do pełnego artykułu. Być może możesz skontaktować się z autorami prywatnie i samodzielnie opublikować odpowiedź na to pytanie, jeśli autorzy chętnie podzielą się wynikiem.