MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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})$?

share|cite|improve this question
Also relevant is Zaslavsky's Theorem, which gives an explicit formula for $R(\mathcal{A})$ in terms of the Mobius function on $L(\mathcal{A})$: $$R(\mathcal{A}) = \sum_{x\in L(\mathcal{A})} (-1)^{r(x)}\mu(\hat{0}, x)$$ I'm not sure how to use this though... – Vlad Firoiu Sep 1 '12 at 4:15
Vlad, this is a really nice question. One quick comment is that the labeling you give above is what is known as an EL-labeling, though usually one would do things in reverse and let $f(x)$ be the minimal $i$ so that $h_i\le x$ and then count descending chains rather than increasing ones. This gives a way to calculate Moebius functions. An excellent reference that may well help you attack this problem is the Park City Math Institute volume on geometric combinatorics, in particular the chapter by Richard Stanley on hyperplane arrangements and the chapter by Michelle Wachs on poset topology. – Patricia Hersh Sep 1 '12 at 13:53

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.

share|cite|improve this answer
Vlad: I see that you are an MIT undergrad. Obviously Richard Stanley would be a great person to ask as to exactly what literature there is related to this question. If I were hunting to see if there were a result like this in the literature, I'd start with the MSRI volume as well as two survey papers of Anders Bj"orner: one on Subspace Arrangements and one on Matroids and Geometric Lattices. Then I'd look at the math reviews for papers that reference these. One reason I suggested Michelle Wachs' chapter is that it describes how to pass from geometric lattices to geometric semilattices. – Patricia Hersh Sep 1 '12 at 22:56
Thank you for all of the references! I'm currently trying to understand your conjectured solution, but I'm not sure what you mean by "vertex" of the arrangement... perhaps the 1-dimensional elements of $L(\mathcal{A})$? – Vlad Firoiu Sep 1 '12 at 23:42
When you intersect hyperplanes, you get lower dimensional subspaces. By vertices, I mean the 0-dimensional subspaces you get this way. These will correspond to the maximal elements in your intersection poset. Let me know if anything else is hard to understand. By the way, I was a grad student at MIT with Stanley, and I mentioned him to you because I think he is happy to give MIT students literature references for such well-defined and interesting questions as this. But I also think you'll learn a lot by working on this question and also trying to understand how it relates to the literature. – Patricia Hersh Sep 2 '12 at 0:40
Yet one more reference just occurred to me: you may also want to compare your idea for hyperplane arrangements to work of Goresky and MacPherson on the topology of the complement of a subspace arrangement -- you can find e.g. the Goresky-MacPherson formula for the Betti numbers in the Bj"orner survey paper on Subspace Arrangements. Like your formula, this formula is also expressed in terms of the intersection poset. Their approach is Morse theoretic, so now I'm really curious how it relates to my conjectural approach. – Patricia Hersh Sep 2 '12 at 1:07
Vlad: I read your labeling as saying each $x\prec y$ is labeled by the biggest hyperplane that is less than $y$ and not less than $x$, which I now see isn't the labeling you gave -- the labeling I mention is often used for geometric lattices. My map from regions to lists of hyperplanes doesn't work with this standard EL-labeling, as you can see by considering a vertex where three or more hyperplanes meet. I wonder if this way of assigning collections of hyperplanes to regions can be used with some $R$-labeling. I was excited that it seemed like a natural map, but it clearly needs more work. – Patricia Hersh Sep 2 '12 at 22:51

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.