Return to Answer

Case 2: $e=2$. Each hyperplane contribute $-t^2$, giving a term $-{n\choose 3}t^2$.

(b) Any $j\geq 4$ hyperplanes meeting at a point $p\in X$. We can choose $p$ in $n$ ways. We then must choose $j$ two-element subsets of $X-p$ whose intersection is empty. There are ${{n-1\choose 2}\choose j}$ ways to choose $j$ two-element subsets of $X-p$. If their intersection is nonempty, then they have a common element $q$ which can be chosen in $n-1$ ways, and then we can choose the remaining elements in ${n-2\choose j}$ ways. This gives the contribution $$ n\sum_{j\geq 4}(-1)^j\left[ {{n-1\choose 2}\choose j}- (n-1){n-2\choose j}\right] $$ $$ \ = n\left[ -1+{n-1\choose 2}-{{n-1\choose 2}\choose 2} + {{n-1\choose 2}\choose 3}-(n-1)(-1+(n-2) -{n-2\choose 2}+{n-2\choose 3}\right]. $$

Case 2: $e=2$. Each hyperplane contributes $-t^2$, giving a term $-{n\choose 3}t^2$.

(b) Any $j\geq 4$ hyperplanes meeting at a point $p\in X$. We can choose $p$ in $n$ ways. We then must choose $j$ two-element subsets of $X-p$ whose intersection is empty. There are ${{n-1\choose 2}\choose j}$ ways to choose $j$ two-element subsets of $X-p$. If their intersection is nonempty, then they have a common element $q$ which can be chosen in $n-1$ ways, and then we can choose the remaining elements in ${n-2\choose j}$ ways. This gives the contribution $$ n\sum_{j\geq 4}(-1)^j\left[ {{n-1\choose 2}\choose j}- (n-1){n-2\choose j}\right] $$ $$ \ = n\left[ -1+{n-1\choose 2}-{{n-1\choose 2}\choose 2} + {{n-1\choose 2}\choose 3}-(n-1)\left(-1+(n-2) -{n-2\choose 2}+{n-2\choose 3}\right)\right]. $$

Addendum. I worked out $d=3$. Here are the details. Let $X$ be an $n$-element "generic" subset of $\mathbb{R}^3$. Thus $X$ determines a set $\mathcal{A}$ of ${n\choose 3}$ hyperplanes. We need to find all subsets of $\mathcal{A}$ with nonempty intersection. A $j$-element subset that intersects in an $e$-dimensional affine space contributes $(-1)^jt^e$ to the characteristic polynomial $\chi(t)$.

Case 1: $e=3$. We take the intersection over the empty set to get $\mathbb{R}^3$. This gives a term $t^3$.

Case 2: $e=2$. Each hyperplane contribute $-t^2$, giving a term $-{n\choose 3}t^2$.

Case 3: $e=1$. (a) Any two hyperplanes intersect in a line (by genericity), giving ${{n\choose 3}\choose 2}t$.

(b) Any $j\geq 3$ hyperplanes containing the same two points $p,q\in X$ meet in a line. There are ${n\choose 2}$ choices for $p,q$ and ${n-2\choose j}$ for the remaining element of $X$ in the hyperplanes. Thus we get a contribution $$ {n\choose 2}\sum_{j\geq 3}(-1)^j {n-2\choose j}t = {n\choose 2}\left[-1+(n-2)-{n-2\choose 3}\right]t. $$

Case 4: $e=0$. (a) Any three hyperplanes intersect at a point, except when all three contain the same two points $p,q\in X$. There are ${{n\choose 3}\choose 3}$ ways to choose three hyperplanes, and ${n\choose 2}{n-2\choose 3}$ ways to choose them so that they intersect in two points of $X$. Hence we get a contribution $$ -\left[ {{n\choose 3}\choose 3}-{n\choose 2}{n-2\choose 3} \right] $$ to the constant term of $\chi(t)$ (the minus sign because the number of hyperplanes is odd).

(b) Any $j\geq 4$ hyperplanes meeting at a point $p\in X$. We can choose $p$ in $n$ ways. We then must choose $j$ two-element subsets of $X-p$ whose intersection is empty. There are ${{n-1\choose 2}\choose j}$ ways to choose $j$ two-element subsets of $X-p$. If their intersection is nonempty, then they have a common element $q$ which can be chosen in $n-1$ ways, and then we can choose the remaining elements in ${n-2\choose j}$ ways. This gives the contribution $$ n\sum_{j\geq 4}(-1)^j\left[ {{n-1\choose 2}\choose j}- (n-1){n-2\choose j}\right] $$ $$ \ = n\left[ -1+{n-1\choose 2}-{{n-1\choose 2}\choose 2} + {{n-1\choose 2}\choose 3}-(n-1)(-1+(n-2) -{n-2\choose 2}+{n-2\choose 3}\right]. $$

(c) Any $j\geq 3$ hyperplanes meeting at $p,q\in X$, together with one additional hyperplane not containing $p$ or $q$. There are ${n\choose 2}$ choices for $p,q$ and ${n-2\choose j}$ ways to choose $j$ hyperplanes containing $p,q$. There are then ${n-2\choose 3}$ ways to choose the additional hyperplane not containing $p$ or $q$. Thus we get the contribution $$ -\left[ \sum_{j\geq 3}(-1)^j{n-2\choose j}\right] {n-2\choose 3} $$ $$ -{n-2\choose 3}{n\choose 2}\left[-1+(n-2)-{n-2\choose 2} \right]. $$

Putting all this together gives the characteristic polynomial $$ t^3-{n\choose 3}t^2+ \frac{1}{72}n(n-1)(n-3)(n^3-2n^2-16n+68)t $$ $$ -\frac{1}{1296}n(n-2)(n-3)(n^6-4n^5-74n^4+698n^3-2129n^2 +2276n-120). $$ The number of regions is $$ \frac{1}{1296}(n-2)(n^8-7n^7-62n^6+938n^5-4295n^4+8429n^3 -4932n^2-2016n-648). $$ The number of bounded regions is $$ \frac{1}{1296}(n-1)(n-2)(n-3)(n^6-3n^5-77n^4+603n^3 -1508n^2+1056n+216). $$ Conceivably there could be an error in the computation, but I checked it for $n=4,5$ by a brute force computation.

This method should extend to any $d$, but the computation will be more complicated, and I am too lazy to work out the details.

This is more of a long comment than an answer. It should be possible to compute the number of regions and number of bounded regions using Whitney's theorem for the characteristic polynomial $\chi(t)$ (Theorem 2.4 of these notes), and Zaslavsky's theorem that the number of regions is $(-1)^d \chi(-1)$, and the number of bounded regions is (in this situation) $\chi(1)$ (Theorem 2.5 of the previous link). We need more than the usual definition of "general position." We want the position to be generic enough for the argument below (generalized to $d$ dimensions) to hold.

Here is the computation for $d=2$. First, the empty intersection (the ambient space $\mathbb{R}^2$) contributes $t^2$ to $\chi(t)$. The ${n\choose 2}$ lines will contribute $-{n\choose 2}t$. Now we must consider all subsets of the lines that intersect in a point $p$. Let $p$ be one of the original $n$ points. Then ${n-1\choose 2}$ pairs of lines intersect in $p$, ${n-1\choose 3}$ triple of lines intersect in $p$, etc., giving a contribution to $\chi(t)$ of $$ {n-1\choose 2}-{n-1\choose 3}+{n-1\choose 4} -\cdots = n-2. $$ We have to multiply this by $n$ since there are $n$ choices for $p$. There are now $3{n\choose 4}$ choices of two lines that don't intersect in one of the original $n$ points, but they still intersect by genericity. Thus we get an additional contribution of $3{n\choose 4}$. It follows that $$ \chi(t) = t^2-{n\choose 2}t+n(n-2)+3{n\choose 4}. $$ The number of regions is $$ \chi(-1) = \frac 18(n-1)(n^3-5n^2+18n-8). $$ The number of bounded regions is $$ \chi(1) = \frac 18(n-1)(n-2)(n^2-3n+4). $$ Can someone extend this argument to $d$ dimensions?

This is more of a long comment than an answer. It should be possible to compute the number of regions and number of bounded regions using Whitney's theorem for the characteristic polynomial $\chi(t)$ (Theorem 2.4 of these notes), and Zaslavsky's theorem that the number of regions is $(-1)^d \chi(-1)$, and the number of bounded regions is (in this situation) $(-1)^d\chi(1)$ (Theorem 2.5 of the previous link). We need more than the usual definition of "general position." We want the position to be generic enough for the argument below (generalized to $d$ dimensions) to hold.

Here is the computation for $d=2$. First, the empty intersection (the ambient space $\mathbb{R}^2$) contributes $t^2$ to $\chi(t)$. The ${n\choose 2}$ lines will contribute $-{n\choose 2}t$. Now we must consider all subsets of the lines that intersect in a point $p$. Let $p$ be one of the original $n$ points. Then ${n-1\choose 2}$ pairs of lines intersect in $p$, ${n-1\choose 3}$ triple of lines intersect in $p$, etc., giving a contribution to $\chi(t)$ of $$ {n-1\choose 2}-{n-1\choose 3}+{n-1\choose 4} -\cdots = n-2. $$ We have to multiply this by $n$ since there are $n$ choices for $p$. There are now $3{n\choose 4}$ choices of two lines that don't intersect in one of the original $n$ points, but they still intersect by genericity. Thus we get an additional contribution of $3{n\choose 4}$. It follows that $$ \chi(t) = t^2-{n\choose 2}t+n(n-2)+3{n\choose 4}. $$ The number of regions is $$ \chi(-1) = \frac 18(n-1)(n^3-5n^2+18n-8). $$ The number of bounded regions is $$ \chi(1) = \frac 18(n-1)(n-2)(n^2-3n+4). $$ Can someone extend this argument to $d$ dimensions?