de¬nes an isomorphism between AH0 and the arrangement AG/e in Rn’1 , proving

(19).

Let n• denote the graph with n vertices and no edges, and let … denote

the empty arrangement in Rn . The theorem will be proved by induction (using

Lemma 2.2) if we show:

(a) Initialization: χn• (t) = χ… (t)

(b) Deletion-contraction:

χG (t) = χG’e (t) ’ χG/e (t)

(20)

To prove (a), note that both sides are equal to tn . To prove (b), observe that

χG’e (q) is the number of colorings of κ : [n] ’ [q] that are proper except possibly

κ(i) = κ(j), while χG/e (q) is the number of colorings κ : [n] ’ [q] of G that are

proper except that κ(i) = κ(j).

Our second proof of Theorem 2.7 is based on M¨bius inversion. We ¬rst obtain

o

a combinatorial description of the intersection lattice L(AG ). Let Hij denote the

hyperplane xi = xj as above, and let F ⊆ E(G). Consider the element X =

ij∈F Hij of L(AG ). Thus

(x1 , . . . , xn ) ∈ X ” xi = xj whenever ij ∈ F.

Let C1 , . . . , Ck be the connected components of the spanning subgraph GF of G

with edge set F . (A subgraph of G is spanning if it contains all the vertices of G.

Thus if the edges of F do not span all of G, we need to include all remaining vertices

as isolated vertices of GF .) If i, j are vertices of some Cm , then there is a path from

i to j whose edges all belong to F . Hence xi = xj for all (x1 , . . . , xn ) ∈ X. On the

other hand, if i and j belong to di¬erent Cm ™s, then there is no such path. Let

¯

F = {e = ij ∈ E(G) : i, j ∈ V (Cm ) for some m},

where V (Cm ) denotes the vertex set of Cm . Figure 6 illustrates a graph G with

¯

a set F of edges indicated by thickening. The set F is shown below G, with the

¯

additional edges F ’ F not in F drawn as dashed lines.

A partition π of a ¬nite set S is a collection {B1 , . . . , Bk } of subsets of S, called

blocks, that are nonempty, pairwise disjoint, and whose union is S. The set of all

partitions of S is denoted ΠS , and when S = [n] we write simply Πn for Π[n] . It

follows from the above discussion that the elements Xπ of L(AG ) correspond to the

LECTURE 2. PROPERTIES OF THE INTERSECTION POSET 27

abcd

abc ac’bd ab’cd

b d abd bcd

acd

a c ab cd

ac bd

bc

Figure 7. A graph G and its bond lattice LG

connected partitions of V (G), i.e., the partitions π = {B1 , . . . , Bk } of V (G) = [n]

such that the restriction of G to each block Bi is connected. Namely,

Xπ = {(x1 , . . . , xn ) ∈ K n : i, j ∈ Bm for some m ’ xi = xj }.

We have Xπ ¤ Xσ in L(A) if and only if every block of π is contained in a block of

σ. In other words, π is a re¬nement of σ. This re¬nement order is the “standard”

ordering on Πn , so L(AG ) is isomorphic to an induced subposet LG of Πn , called

the bond lattice or lattice of contractions of G. (“Induced” means that if π ¤ σ

in Πn and π, σ ∈ L(AG ), then π ¤ σ in L(AG ).) In particular, Πn ∼ L(AKn ).

=

Note that in general LG is not a sublattice of Πn , but only a sub-join-semilattice of

Πn [why?]. The bottom element ˆ of LG is the partition of [n] into n one-element

0

blocks, while the top element ˆ is the partition into one block. The case G = Kn

1

shows that the intersection lattice L(Bn ) of the braid arrangement Bn is isomorphic

to the full partition lattice Πn . Figure 7 shows a graph G and its bond lattice LG

(singleton blocks are omitted from the labels of the elements of LG ).

Second proof of Theorem 2.7. Let π ∈ LG . For q ∈ P de¬ne χπ (q) to be

the number of colorings κ : [n] ’ [q] of G satisfying:

• If i, j are in the same block of π, then κ(i) = κ(j).

• If i, j are in di¬erent blocks of π and ij ∈ E(G), then κ(i) = κ(j).

Given any κ : [n] ’ [q], there is a unique σ ∈ LG such that κ is enumerated by

χσ (q). Moreover, κ will be constant on the blocks of some π ∈ LG if and only if

σ ≥ π in LG . Hence

q |π| = χσ (q) ∀π ∈ LG ,

σ≥π

where |π| denotes the number of blocks of π. By M¨bius inversion,

o

q |σ| µ(π, σ),

χπ (q) =

σ≥π

where µ denotes the M¨bius function of LG . Let π = ˆ We get

o 0.

µ(σ)q |σ| .

(21) χG (q) = χˆ (q) =

0

σ∈LG

28 R. STANLEY, HYPERPLANE ARRANGEMENTS

It is easily seen that |σ| = dim Xσ , so comparing equation (21) with De¬nition 1.3

shows that χG (t) = χAG (t).

Corollary 2.2. The characteristic polynomial of the braid arrangement B n is given

by

χBn (t) = t(t ’ 1) · · · (t ’ n + 1).

Proof. Since Bn = AKn (the graphical arrangement of the complete graph Kn ),

we have from Theorem 2.7 that χBn (t) = χKn (t). The proof follows from equation

(17).

There is a further invariant of a graph G that is closely connected with the

graphical arrangement AG .

De¬nition 2.7. An orientation o of a graph G is an assignment of a direction

i ’ j or j ’ i to each edge ij of G. A directed cycle of o is a sequence of vertices

i0 , i1 , . . . , ik of G such that i0 ’ i1 ’ i2 ’ · · · ’ ik ’ i0 in o. An orientation o is

acyclic if it contains no directed cycles.

A graph G with no loops (edges from a vertex to itself) thus has 2#E(G) orien-

tations. Let R ∈ R(AG ), and let (x1 , . . . , xn ) ∈ R. In choosing R, we have speci¬ed

for all ij ∈ E(G) whether xi < xj or xi > xj . Indicate by an arrow i ’ j that

xi < xj , and by j ’ i that xi > xj . In this way the region R de¬nes an orientation

oR of G. Clearly if R = R , then oR = oR . Which orientations can arise in this

way?

Proposition 2.5. Let o be an orientation of G. Then o = oR for some R ∈ R(AG )

if and only if o is acyclic.

Proof. If oR had a cycle i1 ’ i2 ’ · · · ’ ik ’ i1 , then a point (x1 , . . . , xn ) ∈ R

would satisfy xi1 < xi2 < · · · < xik < xi1 , which is absurd. Hence oR is acyclic.

Conversely, let o be an acyclic orientation of G. First note that o must have a

sink, i.e., a vertex with no arrows pointing out. To see this, walk along the edges

of o by starting at any vertex and following arrows. Since o is acyclic, we can never

return to a vertex so the process will end in a sink. Let jn be a sink vertex of o.

When we remove jn from o the remaining orientation is still acyclic, so it contains

a sink jn’1 . Continuing in this manner, we obtain an ordering j1 , j2 , . . . , jn of [n]

such that ji is a sink of the restriction of o to j1 , . . . , ji . Hence if x1 , . . . , xn ∈ R

satisfy xj1 < xj2 < · · · < xjn then the region R ∈ R(A) containing (x1 , . . . , xn )

satis¬es o = oR .

Note. The transitive, re¬‚exive closure ¯ of an acyclic orientation o is a par-

o

tial order. The construction of the ordering j1 , j2 , . . . , jn above is equivalent to

constructing a linear extension of o.

Let AO(G) denote the set of acyclic orientations of G. We have constructed a

bijection between AO(G) and R(AG ). Hence from Theorem 2.5 we conclude:

Corollary 2.3. For any graph G with n vertices, we have #AO(G) = (’1) n χG (’1).

Corollary 2.3 was ¬rst proved by Stanley in 1973 by a “direct” argument based

on deletion-contraction (see Exercise 7). The proof we have just given based on

arrangements is due to Greene and Zaslavsky in 1983.

Note. Given a graph G on n vertices, let A# be the arrangement de¬ned by

G

xi ’ xj = aij , ij ∈ E(G),

LECTURE 2. PROPERTIES OF THE INTERSECTION POSET 29

where the aij ™s are generic. Just as we obtained equation (14) (the case G = Kn )