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?


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

  • $\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
  • $\begingroup$ an excellent reference ! $\endgroup$ – Suresh Venkat Aug 26 '10 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.