Regions of Hyperplane Arrangements

Question

Let $\mathcal{A}$ be an arrangement of the hyperplanes $h_1, h_2, \ldots h_n$. $\mathcal{A}$ partitions the underlying space $V$ into connected regions, denoted by $R(\mathcal{A})$. I would like to enumerate the regions using the intersection lattice $L(\mathcal{A})$ of $\mathcal{A}$.

Given a hyperplane $h \in \mathcal{A}$, we can define the following two arrangements:
$\mathcal{A}-h$ is the arrangement obtained by removing $h$.
$\mathcal{A}/h$ is the arrangement obtained by contracting to $h$; that is, the new underlying space is $h$, and the new hyperplanes are the intersections of the old hyperplanes with $h$.

It is not hard to see that $|R(\mathcal{A})| = |R(\mathcal{A}-h)| + |R(\mathcal{A}/h)|$. Indeed, each region in $R(\mathcal{A}/h)$ corresponds to a region in $R(\mathcal{A}-h)$ which $h$ cuts in two.

To review, $L(\mathcal{A})$ is the set of intersections of hyperplanes, ordered by reverse inclusion. It has bottom element $\hat{0} = V$, but only has a top element if all of the hyperplanes intersect at a point. Thus, joins (which are intersections) may fail to exist, while meets do always exist. Each element is the join of the hyperplanes below it. (For a better overview of this material, see www.math.rice.edu/~samans/ZaslavskyTheorem.pdf).

For each $x\neq \hat{0}$, let $f(x)$ be the maximal $i$ such that $h_i \leq x$, and let $h(x) = h_{f(x)}$. Define an increasing chain in $L(\mathcal{A})$ to be a sequence $\hat{0} = x_0 \triangleleft x_1 \triangleleft \cdots \triangleleft x_m$ such that $f(x_i)$ is increasing for $i\geq 1$ ($\triangleleft$ denotes covering in the intersection lattice). Note that $x_i = x_{i-1} \lor h(x_i)$. Let $C(\mathcal{A})$ denote the set of all increasing chains.

It is not too hard to see that $|C(\mathcal{A})| = |C(\mathcal{A} - h_1)| + |C(\mathcal{A}/h_1)|$, given an appropriate ordering of the atoms in $\mathcal{A}/h_1$. It then follows by induction that $|C(\mathcal{A})| = |R(\mathcal{A})|$ and that $|C(\mathcal{A})|$ does not depend on initial order of the hyperplanes.

My question is then: does there exist a "natural" bijection between $R(\mathcal{A})$ and $C(\mathcal{A})$?

Answer 1

There is an inductive construction of the bijection you seek in a paper of Ken Jewell and Peter Orlik, in the proceedings of Arrangements in Boston (1998), published in Topology and Its Applications. Your increasing chains are in bijection with nbc (= "no-broken-circuit) sets in the arrangement. (The nbc set associated with $x_0 < \cdots < x_m$ is {f(x_0), ... , f(x_n)}, identifying hyperplanes with their labels.) Jewell and Orlik assign a chamber to each nbc set, bijectively, in Lemma 3.14 of that paper. Their bijection is built up one hyperplane at a time, that is, by deletion-contraction.

Answer 2

Here's a conjectural solution, motivated by the idea of a "line shelling". Begin by choosing a "generic" nonzero vector $c$ in your ambient space, i.e. a vector such that it spans a line which crosses all of your hyperplanes.

Next, associate each vertex $v$ in the hyperplane arrangement to the unique region $R$ having the property that the dot product $c\cdot x$ is maximized on $R$ at $v$. Now assign to each vertex $v$ the set of hyperplanes which bound this region $R$ and pass through $v$. Each such $R$ is then bijectively mapped to the increasing chain in the intersection poset labeled by this list of chosen hyperplanes arranged in ascending order.

Similarly, label each of the remaining regions $R$ by its set of bounding hyperplanes $\mathcal{H}$ which have the property that for each chosen $\mathcal{H}$ there is another bounding hyperplane $\mathcal{H'}$ of $R$ and a line segment going in the direction $c$ which starts at a point $p'$ on $\mathcal{H'}$ and ends at a point $p$ on $\mathcal{H}$, with $c\cdot x$ increasing as we progress along the segment from $p'$ to $p$. Bijectively map each of these regions $R$ to the increasing chain in the intersection poset labeled by its chosen collection of hyperplanes, again listed in increasing order.

It would be great if you or someone else wants to figure out whether this conjecture is correct. I wouldn't be surprised though if someone has thought about your question before -- your question certainly ties in with a lot of interesting work in the literature.