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$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Aug 26, 2010 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$ Commented Aug 26, 2010 at 2:29
-