Equation (11) can be rewritten as

(’1)rk(x) µ(x).

r(A) =

x∈L(A)

(Theorem 3.10 will show that (’1)rk(x) µ(x) > 0, so we could also write |µ(x)| for

this quantity.) It is easy to extend this result to count faces of A of all dimensions,

not just the top dimension n. Let fk (A) denote the number of k-faces of the real

arrangement A.

Theorem 2.6. We have

(’1)dim(x)’dim(y) µ(x, y)

(15) fk (A) =

x¤y in L(A)

dim(x)=k

|µ(x, y)|.

(16) =

x¤y in L(A)

dim(x)=k

Proof. As mentioned above, every face F is a region of a unique Ax for x ∈ L(A),

viz., x = a¬(F ). In particular, dim(F ) = dim(x). Hence if dim(F ) = k, then r(Ax )

is the number of k-faces of A contained in x. By Theorem 2.5 and equation (7) we

get

r(Ax ) = (’1)dim(y)’dim(x) µ(x, y),

y≥x

24 R. STANLEY, HYPERPLANE ARRANGEMENTS

where we are dealing with the poset L(A). Summing over all x ∈ L(A) of dimension

k yields (15), and (16) then follows from Theorem (3.10) below.

2.3. Graphical arrangements

There are close connections between certain invariants of a graph G and an asso-

ciated arrangement AG . Let G be a simple graph on the vertex set [n]. Let E(G)

denote the set of edges of G, regarded as two-element subsets of [n]. Write ij for

the edge {i, j}.

De¬nition 2.5. The graphical arrangement AG in K n is the arrangement

xi ’ xj = 0, ij ∈ E(G).

Thus a graphical arrangement is simply a subarrangement of the braid arrange-

ment Bn . If G = Kn , the complete graph on [n] (with all possible edges ij), then

A Kn = B n .

De¬nition 2.6. A coloring of a graph G on [n] is a map κ : [n] ’ P. The coloring

κ is proper if κ(i) = κ(j) whenever ij ∈ E(G). If q ∈ P then let χG (q) denote the

number of proper colorings κ : [n] ’ [q] of G, i.e., the number of proper colorings

of G whose colors come from 1, 2, . . . , q. The function χG is called the chromatic

polynomial of G.

For instance, suppose that G is the complete graph Kn . A proper coloring

κ : [n] ’ [q] is obtained by choosing a vertex, say 1, and coloring it in q ways.

Then choose another vertex, say 2, and color it in q ’ 1 ways, etc., obtaining

χKn (q) = q(q ’ 1) · · · (q ’ n + 1).

(17)

A similar argument applies to the graph G of Figure 5. There are q ways to color

vertex 1, then q ’ 1 to color vertex 2, then q ’ 1 to color vertex 3, etc., obtaining

= q(q ’ 1)(q ’ 1)(q ’ 2)(q ’ 1)(q ’ 1)(q ’ 2)(q ’ 2)(q ’ 3)

χG (q)

= q(q ’ 1)4 (q ’ 2)3 (q ’ 3).

Unlike the case of the complete graph, in order to obtain this nice product formula

one factor at a time only certain orderings of the vertices are suitable. It is not

always possible to evaluate the chromatic polynomials “one vertex at a time.” For

instance, let H be the 4-cycle of Figure 5. If a proper coloring κ : [4] ’ [q] satis¬es

κ(1) = κ(3), then there are q choices for κ(1), then q ’ 1 choices each for κ(2) and

κ(4). On the other hand, if κ(1) = κ(3), then there are q choices for κ(1), then

q ’ 1 choices for κ(3), and then q ’ 2 choices each for κ(2) and κ(4). Hence

= q(q ’ 1)2 + q(q ’ 1)(q ’ 2)2

χH (q)

= q(q ’ 1)(q 2 ’ 3q + 3).

For further information on graphs whose chromatic polynomial can be evaluated

one vertex at a time, see Corollary 4.10 and the note following it.

It is easy to see directly that χG (q) is a polynomial function of q. Let ei (G)

denote the number of surjective proper colorings κ : [n] ’ [i] of G. We can choose

an arbitrary proper coloring κ : [n] ’ [q] by ¬rst choosing the size i = #κ([n]) of

its image in q ways, and then choose κ in ei ways. Hence

i

n

q

(18) χG (q) = ei .

i

i=0

LECTURE 2. PROPERTIES OF THE INTERSECTION POSET 25

6 8

9

4 3

5 4

7

2

1 2

3

1

G H

Figure 5. Two graphs

Since q = q(q’1) · · · (q’i+1)/i!, a polynomial in q (of degree i), we see that χG (q)

i

is a polynomial. We therefore write χG (t), where t is an indeterminate. Moreover,

any surjection (= bijection) κ : [n] ’ [n] is proper. Hence en = n!. It follows from

equation (18) that χG (t) is monic of degree n. Using more sophisticated methods

we will later derive further properties of the coe¬cients of χG (t).

Theorem 2.7. For any graph G, we have χAG (t) = χG (t).

First proof. The ¬rst proof is based on deletion-restriction (which in the

context of graphs is called deletion-contraction). Let e = ij ∈ E(G). Let G ’ e

(also denoted G\e) denote the graph G with edge e deleted, and let G/e denote G

with the edge e contracted to a point and all multiple edges replaced by a single

edge (i.e., whenever there is more than one edge between two vertices, replace these

edges by a single edge). (In some contexts we want to keep track of multiple edges,

but they are irrelevant in regard to proper colorings.)

4 4 4

2 2

e 5 23

5 5

1 1 1

3 3

G’e G/e

G

Let H0 ∈ A = AG be the hyperplane xi = xj . It is clear that A’{H0 } = AG’e .

We claim that

AH0 = AG/e ,

(19)

so by Deletion-Restriction (Lemma 2.2) we have

χAG (t) = χAG’e (t) = χAG/e (t).

∼

=

To prove (19), de¬ne an a¬ne isomorphism • : H0 ’ Rn’1 by

(x1 , x2 , . . . , xn ) ’ (x1 , . . . , xi , . . . , xj , . . . , xn ),

ˆ

where xj denotes that the jth coordinate is omitted. (Hence the coordinates in

ˆ

are 1, 2, . . . , ˆ . . . , n.) Write Hab for the hyperplane xa = xb of A. If neither

n’1

j,

R

of a, b are equal to i or j, then •(Hab © H0 ) is the hyperplane xa = xb in Rn’1 . If

a = i, j then •(Hia © H0 ) = •(Haj © H0 ), the hyperplane xa = xi in Rn’1 . Hence •

26 R. STANLEY, HYPERPLANE ARRANGEMENTS

G

F

¯

Figure 6. A graph G with edge subset F and closure F