Verweis auf untere Grenze des Trennzeichens in einem Raster?

13

Es ist leicht zu überprüfen, ob angesichts des d-dimensionalen Gitters der ganzzahligen Punkte mit der regulären Nachbarschaft ein Trennzeichen der Größe n d - 1 gefunden werden kann (wählen Sie einfach eine mittlere Hyperebene aus und entfernen Sie alle seine Eckpunkte). Es ist auch nicht zu hart (aber definitiv nicht sofort) , um sicherzustellen , dass jeder Separator von Größe sein muss Ω ( n d - 1 ) . Kennt jemand einen Bezug dazu?{1,,n}dnd-1Ω(nd-1)

Sariel Har-Peled
quelle

Antworten:

12

Sieht aus wie das Buch "Graph Separators, with applications" von Arnold Rosenberg und Lenwood Heath, das Ihre Frage beantwortet (siehe Abschnitt 4.3.4.), Aber es kann vorkommen, dass ich ihre Schreibweise missverstanden habe (bitte lassen Sie es mich wissen). Auf jeden Fall ist dieses Buch eine sehr umfassende Referenz zu Trennzeichen.

BEARBEITEN. Hier finden Sie einen Download-Link zu Springer: http://www.springerlink.com/content/978-0-306-46464-5

Grigory Yaroslavtsev
quelle
In der Tat ist es Anwendung 4.2.9 auf Seite 177 dieses Buches. Ich wusste nicht, dass dieses Buch existiert ... Jetzt müsste ich es bekommen. Vielen Dank.
Sariel Har-Peled
eine hervorragende referenz!
Suresh Venkat