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?


1 Answer 1


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.

  • $\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$ Aug 26, 2010 at 2:29
  • $\begingroup$ an excellent reference ! $\endgroup$ Aug 26, 2010 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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