Counting Regions in Hyperplane Arranglements

Question

Consider the following:

1) How many connected regions can $n$ hyperplanes form in $\mathbb R^d$?

2) What if the set of hyperplanes are homogeneous?

3) Given a set of $n$ pairs of hyperplanes, such that each pair is parallel, what is the maximum number of regions that can be formed?

I saw here,here and here that the answer to (1) is $$f(d,n)=\sum_{i=0}^d {n \choose i}$$

However I find it non-trivial to generalize the proof of $\mathbb R^2$ that was provided to $\mathbb R^d$ (without using "lower"/"upper" descriptions). Is there any "nice" way to show it recursively?

Q3 is what I'm really after.

Any ideas?

Answer 1

Suppose we have $n$ sets of $r$ parallel hyperplanes in $\mathbb{R}^d$ in generic position. There are $r^k\binom nk$ ways to choose $k$ of them that intersect in a flat $x$. The interval from $\hat{0}$ to $x$ in the intersection poset is a boolean algebra, so the Mobius function is given by $\mu(\hat{0},x)=\pm 1$. Thus by Zaslavsky's theorem, the number of regions is $\sum_{k=0}^d r^k\binom nk$.

Answer 2

Use Radon's theorem to show that homogeneous hyperplanes $w$ can shatter (i.e., assign all possible sign sequences via $x\mapsto\text{sign}(<w,x>)$ at most $d$ points. This is an upper bound on the VC-dimension on hyperplanes (which turns out to be tight). Then use the Sauer-Shelah lemma to bound the number of behaviors that the hyperplanes can attain on $n$ points

That accounts for the formula $\sum_{i=1}^d {n\choose i}$.

As for pairs of hyperplanes, I'll use a very crude bound for VC-dimension of intersections of pairs of sets from a VC-class of dimension $d$, see Theorem 3.6 in Kearns-Vazirani or this paper by Baum and Haussler, to get that the VC-dimension of the collection of pairs of hyperplanes in $d$ dimensions is at most $20d$. You can then apply Sauer-Shelah to this new value of VC-dimension.