3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ This is all explained in e.g. Stanley's notes on hyperplane arrangements: www-math.mit.edu/~rstan/arrangements/arr.html $\endgroup$ Commented Jan 1, 2017 at 17:32
  • $\begingroup$ @SamHopkins: You just went ahead of me. :-) $\endgroup$ Commented Jan 1, 2017 at 17:34
  • $\begingroup$ The proof (page 18) is not as clear as one may think :) $\endgroup$ Commented Jan 1, 2017 at 18:12
  • 2
    $\begingroup$ For the proof on page 18, see the errata at www-math.mit.edu/~rstan/arrangements/errata.pdf. $\endgroup$ Commented Jan 1, 2017 at 18:52
  • $\begingroup$ Much better now :) $\endgroup$ Commented Jan 1, 2017 at 19:11

2 Answers 2

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ For a much less elegant proof of this formula (by people who don't know any theorems) see Lemma 3 in this paper: arxiv.org/abs/1508.03181 $\endgroup$ Commented Jan 3, 2017 at 21:12
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.