Biorąc pod uwagę n rozróżnialnych punktów d-wymiarowych, jaka jest największa liczba różnych sposobów ich liniowego rozdzielenia?

Question

Załóżmy, że mamy $n$ rozróżnialne punkty w $\mathbb{R}^d$. Co jest$f(n, d)$, największą liczbę różnych sposobów, w jakie możemy je rozdzielić za pomocą pojedynczej hiperpłaszczyzny? Nie uważam zamiany „lewej” i „prawej” strony samolotu za inne.

Znalazłem następujące pytanie dla$d = 2$ sprawa, więc $f(n, 2) = \binom{n}{2} + 1$.

Możesz założyć, że punkty są w pozycji umożliwiającej największą liczbę separacji. Dla$d = 2$ pokazano, że to nie ma znaczenia (poza brakiem współliniowości), ale nie wiem, czy dotyczy to również wyższych wymiarów (z punktami w pozycji ogólnej).

Answer 1

Zakładając $n$punktów w położeniu ogólnym , jak pokazano w artykule „Liczba podziałów zbioru N punktów w k wymiarach indukowanych przez hiperpłaszczyzny” EF Hardinga, funkcja, której szukasz, to:

$$f(n,d) = \sum_{k=0}^{d}{n-1 \choose k}$$