It is easy to verify that given the d dimensional grid of the integer points $\{1,\ldots,n\}^d$, with the regular adjacency, one can find a separator of size $n^{d-1}$ (just pick any middle hyperplane, and remove all its vertices). It is also not too hard (but definitely not immediate) to verify that any separator has to be of size $\Omega(n^{d-1})$. Anybody knows a refenence to this?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Looks like the book "Graph separators, with applications" by Arnold Rosenberg and Lenwood Heath answers your question (see section 4.3.4.), but it could happen that I misunderstood their notation (please, let me know). Anyway, this book is a very comprehensive reference on separators.
EDIT. Here is a download link on Springer: http://www.springerlink.com/content/978-0-306-46464-5
answered Aug 26 '10 at 0:32
-
$\begingroup$ In fact, it is application 4.2.9 on page 177 of this book. I did not know that this book existed... Now I would have to get it. Thanks. $\endgroup$ – Sariel Har-Peled Aug 26 '10 at 2:29
-
