Référence à la borne inférieure du séparateur dans une grille?

Il est facile de vérifier que, étant donné la grille dimensionnelle d des points entiers , avec la contiguïté régulière, on peut trouver un séparateur de taille n d - 1 (il suffit de choisir n'importe quel hyperplan central et de supprimer tout ses sommets). Il n'est pas non plus trop difficile (mais certainement pas immédiat) de vérifier que tout séparateur doit être de taille Ω ( n d - 1 ) . Quelqu'un connaît une référence à cela?$\{1,\ldots,n\}^d$$n^{d-1}$$\Omega(n^{d-1})$

On dirait que le livre "Graph separators, with applications" d'Arnold Rosenberg et Lenwood Heath répond à votre question (voir section 4.3.4.), Mais il peut arriver que j'aie mal compris leur notation (faites-le moi savoir). Quoi qu'il en soit, ce livre est une référence très complète sur les séparateurs.

ÉDITER. Voici un lien de téléchargement sur Springer: http://www.springerlink.com/content/978-0-306-46464-5