# Reference to lower bound on separator in a grid?

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

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

• 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. – Sariel Har-Peled Aug 26 '10 at 2:29
• an excellent reference ! – Suresh Venkat Aug 26 '10 at 4:26