Skip to main content
2 of 4
inserted factor of (-1)^d before \chi(1)
Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279

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?

Richard Stanley
  • 50.8k
  • 14
  • 155
  • 279