Какова ширина пути 3D-сетки (сетка или решетка) с длиной стороны k?

12

Я задавал этот вопрос несколько недель назад в mathoverflow , но не получил ответа.

Здесь под 3D-сеткой с длиной стороны я имею в виду граф G = ( V , E ) с V = { 1 , , k } 3 и E = { ( ( a , b , c ) , ( x , y , z ) ) | а - х | + | б - у | + | сkG=(V,E)V={1,,k}3 , т. Е. Узлы размещаются в трехмерных целочисленных координатах между 1 и k , и узел соединяется не более чем с 6 другими узлами, которые отличаются точно одной координатой на одну.E={((a,b,c),(x,y,z))|ax|+|by|+|cz|=1}k

Как называется этот график? Я буду использовать 3D-сетку, но, возможно, другие люди привыкли к 3D-сетке или 3D-решетке.

Какова ширина или траектория этого графика? Это уже где-то опубликовано?

Я уже знаю , что , то есть это действительно меньше , чем к 2 . Для меня это говорит о том, что стандартные аргументы, показывающие, что 2D-сетка k × k имеет ширину дерева и ширину пути k , не будут легко обобщаться.tw(G)=(3/4)k2+O(k)k2k×kk

Чтобы увидеть это, рассмотрим разложение пути, которое «охватывает» сетку, используя в основном наборы узлов вида . Соблюдайте | S c | ( 3 / 4 ) к 2 + O ( K ) , S 3 / 2 к быть самым большим таким набором. Наборы между S c иSc={(x,y,z)x+y+z=c}|Sc|(3/4)k2+O(k)S3/2kSc создаются путем перемещения по линии и требуют O ( k ) дополнительных узлов, чтобы быть разделителями. Точнее, использовать множества S c , d = { ( x , y , z ) ( x + y + z = c x d ) ( x + y + z = c x d ) }Sc+1O(k)Sc,d={(x,y,z)(x+y+z=cxd)(x+y+z=cxd)}как разложение пробега .G

У меня также есть идея для доказательства, которое показывает , но оно еще не закончено.tw(G)=Ω(k2)

Рико Джейкоб
источник
для c = k / 2 . Я что-то пропустил? |Sc|=Ω(k2)c=k/2
Сариэль Хар-Пелед
Конечно. Но используется только в верхней границе. Что меня действительно волнует, так это нижняя граница. Sc
Рико Джейкоб
Вас может заинтересовать этот документ: springerlink.com/content/3nmjlc1g5emx9vpk . Если вы можете вычислить «номер очереди» вашего графа, то вам будет предоставлена нижняя граница на его пути-ширины , используя теорему 1 , которая гласит , что для любого графа G . qn(G)pw(G)G
Матье Шапель
Ой. Понимаю. Вы имели в виду . (3/4)k2
Сариэль Хар-Пелед
1
@Sariel: я редактировал вопрос, чтобы избежать той же путаницы.
Цуёси Ито

Ответы:

13

Ширина пути может быть определена как следствие некоторых известных результатов. FitzGerald [2] показал, что полоса пропускания P 3 k составляет 3Pk3Pk334k2+12kPk334k2+12k

Pk3

К вашему сведению: я только что отправил англоязычную версию нашей статьи в arXiv.

  1. Б. Боллобас и И. Лидер, Сжатия и изопериметрические неравенства, Дж. Комбин. Теория Сер. A 56 (1991) 47-62.
  2. CH FitzGerald, Оптимальное индексирование вершин графов, Матем. Комп. 28 (1974), 825-831.
  3. Л. Харпер, Оптимальные нумерации и изопериметрические задачи на графах, Дж. Комбин. Теория 1 (1966) 385-393.
  4. n
  5. n
Йота Отачи
источник
Спасибо, что любезно поделились своим новым результатом (и докладом!) Также, добро пожаловать в TCS SE :)
Сянь-Чи Чанг 張顯 之
@ Сянь-Chih: Вы заставили меня решить поделиться нашим результатом :-) Спасибо. На самом деле, я тоже новичок в arXiv.
Йота Отачи
6

Путь прохождения трехмерных сеток был изучен Рёхей Суда , Йотой Отачи и Коичи Ямазаки в статье « Путь прохождения трехмерных сеток» , IEICE Tech. Отчет, 2009.

В реферате статьи утверждается, что

В этой статье мы даем траекторию 3-мерных сеток в закрытом виде, определяя ширину их вершинных границ.

Однако точная граница не указана в аннотации, и в настоящее время я не могу получить доступ к полной статье. Возможно, вы можете связаться с авторами в частном порядке и опубликовать ответ на этот вопрос самостоятельно, если авторы готовы поделиться результатом.

Сянь-Чжи Чан 張顯 之
источник
Обратите внимание, что статья написана на японском языке.
Цуёси Ито
@Tsuyoshi: Да, нам может понадобиться ваша помощь :)
Сянь-Чи Чанг 之 之
4
P×Pm×Pnm+mn+2m(+mn12)2Pkkmn
pw(Pk3)=34k2+O(k)
Благодарю. Похоже, я не должен чувствовать себя плохо из-за того, что сам не нашел эту ссылку. Мне интересно узнать подробности.
Рико Джейкоб