Odniesienie do dolnej granicy separatora w siatce?

Łatwo jest zweryfikować, że biorąc pod uwagę wymiarową siatkę punktów całkowitych , przy regularnym sąsiedztwie można znaleźć separator o rozmiarze (wystarczy wybrać dowolny środkowy hiperpłaszczyzna i usuń wszystkie jego wierzchołki). Nie jest też zbyt trudne (ale zdecydowanie nie natychmiastowe) sprawdzenie, czy każdy separator musi mieć rozmiar \ Omega (n ^ {d-1}) . Czy ktoś wie, na czym to polega?$\{1,\ldots,n\}^d$$n^{d-1}$$\Omega(n^{d-1})$

Wygląda na to, że książka „Separatory wykresów z aplikacjami” autorstwa Arnolda Rosenberga i Lenwooda Heatha odpowiada na twoje pytanie (patrz sekcja 4.3.4.), Ale może się zdarzyć, że źle zrozumiałem ich zapis (proszę daj mi znać). W każdym razie ta książka jest bardzo obszernym odniesieniem do separatorów.

EDYTOWAĆ. Oto link do pobrania na Springer: http://www.springerlink.com/content/978-0-306-46464-5