Wie breit ist das 3D-Gitter (Gitter oder Gitter) mit der Seitenlänge k?

12

Ich habe diese Frage vor einigen Wochen bei mathoverflow gestellt , aber keine Antwort erhalten.

Hier meine ich mit 3D-Gitter der Seitenlänge den Graphen G = ( V , E ) mit V = { 1 , , k } 3 und E = { ( ( a , b , c ) , ( x , y , z ) ) | a - x | + | b - y | + | ckG=(V,E)V={1,,k}3 , dh die Knoten liegen an dreidimensionalen Ganzzahlkoordinaten zwischen 1 und k , und ein Knoten ist mit höchstens 6 anderen Knoten verbunden, die sich in genau einer Koordinate um eine unterscheiden.E={((a,b,c),(x,y,z))|ax|+|by|+|cz|=1}k

Wie heißt dieses Diagramm? Ich werde 3D-Gitter verwenden, aber vielleicht sind 3D-Gitter oder 3D-Gitter das, was andere Leute gewohnt sind.

Wie breit oder breit ist dieser Graph? Wird das schon irgendwo veröffentlicht?

Ich weiß schon , dass , dh es ist wirklich kleiner als k 2 . Für mich deutet dies darauf hin, dass sich die Standardargumente, die zeigen, dass das k × k- 2D-Gitter eine Baumbreite und eine Pfadbreite k aufweist , nicht leicht verallgemeinern lassen.tw(G)=(3/4)k2+O(k)k2k×kk

Um dies zu sehen, betrachten wir eine Pfadzerlegung, die das Gitter hauptsächlich unter Verwendung von Knotensätzen der Form "abtastet" . Beachten Sie | S c | ( 3 / 4 ) k 2 + O ( k ) , S 3 / 2 k die größte derartige eingestellt wird. Die Mengen zwischen S c undSc={(x,y,z)x+y+z=c}|Sc|(3/4)k2+O(k)S3/2kSc werden durch Abtasten mit einer Linie erzeugt und benötigen O ( k ) zusätzliche Knoten als Trennzeichen. Genauer gesagt, benutze die Mengen 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)}als Weg Zersetzung von .G

Ich habe auch eine Idee für einen Beweis, der , der aber noch nicht fertig ist.tw(G)=Ω(k2)

Riko Jacob
quelle
für c = k / 2 . Vermisse ich etwas? |Sc|=Ω(k2)c=k/2
Sariel Har-Peled
Sicher. Aber ist nur in der oberen Grenze verwendet. Was mich wirklich interessiert, ist eine Untergrenze. Sc
Riko Jacob
Dieses Papier könnte Sie interessieren: springerlink.com/content/3nmjlc1g5emx9vpk . Wenn Sie die "Warteschlangennummer" Ihres Graphen berechnen können, erhalten Sie eine Untergrenze für seine Pfadbreite unter Verwendung von Satz 1, der besagt, dass für jeden Graphen G ist . qn(G)pw(G)G
Mathieu Chapelle
Oh. Aha. Sie bedeuten . (3/4)k2
Sariel Har-Peled
1
@Sariel: Ich habe die Frage bearbeitet, um die gleiche Verwirrung zu vermeiden.
Tsuyoshi Ito

Antworten:

13

Die Pfadbreite von kann als eine Folge einiger bekannter Ergebnisse bestimmt werden. FitzGerald [2] zeigen , dass die Bandbreite der P 3 k ist 3Pk3Pk3. Harper [3] zeigte eine Bedingung, bei der die Pfadbreite und Bandbreite eines Graphen gleich sind, wenn dieser die Bedingung erfüllt. Moghadam [4,5] und Bollobás und Leader [1] zeigten unabhängig voneinander, dass jedes mehrdimensionale Gitter Harpers Bedingung erfüllt. Diese Ergebnisse implizieren, dass die Pfadbreite vonP 3 k ebenfalls3 ist34k2+12kPk3.34k2+12k

In unserem von Hsien-Chih erwähnten Aufsatz haben wir das Ergebnis von FitzGerald verallgemeinert, wie Yoshio erklärte. Ich glaube, die Baumbreite von ist nicht bekannt.Pk3

Zu Ihrer Information: Ich habe gerade eine englische Version unseres Papiers an arXiv gesendet.

  1. B. Bollobás und I. Leader, Kompressionen und isoperimetrische Ungleichungen, J. Combin. Theory Ser. A 56 (1991) 47-62.
  2. CH FitzGerald, Optimale Indizierung der Scheitelpunkte von Graphen, Math. Comp. 28 (1974), 825 & ndash; 831.
  3. LH Harper, Optimale Nummerierungen und isoperimetrische Probleme in Graphen, J. Combin. Theory 1 (1966) 385 & ndash; 393.
  4. HS Moghadam, Komprimierungsoperatoren und eine Lösung für das Bandbreitenproblem des Produkts von Pfaden, Ph.D. Diplomarbeit, Universität von Kalifornien, Riverside (1983).n
  5. HS Moghadam, Bandbreite des Produkts von Pfaden, Congr. Nummer. 173 (2005) 3-15.n
Yota Otachi
quelle
Vielen Dank für die freundliche Mitteilung Ihres neuen Ergebnisses (und Ihrer Arbeit!). Willkommen auch bei TCS SE :)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih: Du hast mich dazu gebracht, unser Ergebnis zu teilen :-) Danke. Tatsächlich bin ich auch neu bei arXiv.
Yota Otachi
6

Die Pfadbreite von 3D-Gittern wurde von Ryohei Suda, Yota Otachi und Koichi Yamazaki in der Arbeit Pathwidth of 3-dimensional grids , IEICE Tech, untersucht. Bericht, 2009.

Es wird in der Zusammenfassung des Papiers behauptet, dass

In diesem Artikel geben wir die Pfadbreite von dreidimensionalen Gittern in geschlossener Form an, indem wir deren Scheitelpunkt-Grenzbreite bestimmen.

Die genaue Grenze ist jedoch nicht in der Zusammenfassung angegeben, und ich kann derzeit nicht auf das vollständige Papier zugreifen. Vielleicht können Sie sich privat an die Autoren wenden und diese Frage selbst beantworten, wenn die Autoren bereit sind, das Ergebnis mitzuteilen.

Hsien-Chih Chang 張顯 張顯
quelle
Beachten Sie, dass das Papier in Japanisch geschrieben ist.
Tsuyoshi Ito
@ Tsuyoshi: Ja, wir brauchen vielleicht deine Hilfe :)
Hsien-Chih Chang 張顯 張顯
4
Ich habe physischen Zugang zum Manuskript (und kann Japanisch verstehen). Nach Ansicht der Autoren, die pathwidth von ist l m , wenn l + m n + 2 und l m - ( l + m - n - 1P×Pm×Pnm+mn+2andernfalls, wennPkein Pfad mitkEcken ist, undmn. m(+mn12)2Pkkmn
Yoshio Okamoto
@Yoshio: Dies verdient eine Antwort, da es p w ( P 3 k ) = 3 impliziert, was die Frage beantwortet. pw(Pk3)=34k2+O(k)
Hsien-Chih Chang 張顯 張顯
Vielen Dank. Sieht so aus, als müsste ich mich nicht schlecht fühlen, wenn ich diese Referenz nicht selbst finde. Ich bin neugierig auf die Details.
Riko Jacob