<p>Looks like the book &quot;<a href="https://doi.org/10.1007/b115747" rel="nofollow noreferrer">Graph separators, with applications</a>&quot; 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.</p>

CC BY-SA 2.5
2010-08-26T02:29:49.387Z
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
CC BY-SA 2.5
2010-08-26T04:26:58.670Z
an excellent reference !
Suresh Venkat
CC BY-SA 4.0
2010-08-26T00:32:26.050Z
2022-10-11T07:55:59.760Z
2022-10-11T07:55:59.760Z
Grigory Yaroslavtsev
<p>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?</p>

<reference-request><cg.comp-geom><lower-bounds>
Reference to lower bound on separator in a grid?
Sariel Har-Peled
# Reference to lower bound on separator in a grid?

(Asked by: username_0 on 2010-08-25)

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?

**Tags:** reference-request, cg.comp-geom, lower-bounds

---

## 1 answers

### Answer by username_1 on 2010-08-26. Score: 13 | Accepted answer

Looks like the book "[Graph separators, with applications](https://doi.org/10.1007/b115747)" 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.

> **Comments:**
> **username_0**: 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.  
> **username_2**: an excellent reference !  

---

