0 1

1 ¤ i ¤ j ’ 1. By the de¬nition of E-labeling, there exists a unique re¬nement

ˆ = y 0 = x0 xn = yj = ˆ

··· ··· ···

0 x1 x a1 = y 1 xa1 +1 x a2 = y 2 1

satisfying

»(x0 , x1 ) ¤ »(x1 , x2 ) ¤ · · · ¤ »(xa1 ’1 , xa1 )

»(xa1 , xa1 +1 ) ¤ »(xa1 +1 , xa1 +2 ) ¤ · · · ¤ »(xa2 ’1 , xa2 )

···

Thus if »(xi’1 , xi ) > »(xi , xi+1 ), then i ∈ S, so (27) is satis¬ed. Conversely, given

a maximal chain ˆ = x0 x1 · · · xn = ˆ satisfying the above conditions on »,

0 1

let yi = xai . Therefore we have a bijection between the chains counted by ±P (S)

and the maximal chains satisfying (27), so the claim follows.

Now for S ⊆ [n ’ 1] de¬ne

(’1)#(S’T ) ±P (T ).

(28) βP (S) =

T ⊆S

The function βP is called the ¬‚ag h-vector of P . A simple Inclusion-Exclusion

argument gives

(29) ±P (S) = βP (T ),

T ⊆S

for all S ⊆ [n’1]. It follows from the claim and equation (29) that βP (T ) is equal to

the number of maximal chains ˆ = x0 x1 · · · xn = ˆ such that »(xi ) > »(xi+1 )

0 1

if and only if i ∈ T . In particular, βP ([n ’ 1]) is equal to the number of strictly

decreasing maximal chains ˆ = x0 x1 · · · xn = ˆ of P , i.e.,

0 1

»(x0 , x1 ) > »(x1 , x2 ) > · · · > »(xn’1 , xn ).

Now by (28) we have

(’1)n’1’#T ±P (T )

βP ([n ’ 1]) =

T ⊆[n’1]

(’1)n’k

=

k≥1 ˆ 0 <y1 <···<yk =ˆ

0=y 1

= (’1)n (’1)k ck ,

k≥1

where ci is the number of chains 0 = y0 < y1 < · · · < yi = ˆ in P . The proof now

ˆ 1

follows from Philip Hall™s theorem (Lemma 4.4).

We come to the main result of this subsection, a combinatorial interpretation

of the coe¬cients of the characteristic polynomial χM (t) for any matroid M .

LECTURE 4. BROKEN CIRCUITS AND MODULAR ELEMENTS 45

5 54 5 4 2

42

15 1 5

4 2

3 55 4

32

1 4 5

2 3

1 2 3 4 5

˜

Figure 3. The edge labeling » of a geometric lattice L(M )

Theorem 4.12. Let M be a matroid of rank n with a linear ordering x1 < x2 <

· · · < xm of its points (so the broken circuit complex BC(M ) is de¬ned), and let

0 ¤ i ¤ n. Then

(’1)i [tn’i ]χM (t) = fi’1 (BC(M )).

Proof. We may assume M is simple since the “simpli¬cation” M has the same

lattice of ¬‚ats and same broken circuit complex as M (Exercise 1). The atoms x i of

˜

L(M ) can then be identi¬ed with the points of M . De¬ne a labeling » : E(L(M )) ’

P as follows. Let x y in L(M ). Then set

˜

»(x, y) = max{i : x ∨ xi = y}.

(30)

˜

Note that »(x, y) is de¬ned since L(M ) is atomic.

As an example, Figure 3 shows the lattice of ¬‚ats of the matroid M of Figure 1

with the edge labeling (30).

Claim 1. De¬ne » : E(L(M )) ’ P by

˜

»(x, y) = m + 1 ’ »(x, y).

Then » is an E-labeling.

To prove this claim, we need to show that for all x < y in L(M ) there is a

unique saturated chain x = y0 y1 · · · yk = y satisfying

˜ ˜ ˜

»(y0 , y1 ) ≥ »(y1 , y2 ) ≥ · · · ≥ »(yk’1 , yk ).

The proof is by induction on k. There is nothing to prove for k = 1. Let k > 1 and

assume the assertion for k ’ 1. Let

j = max{i : xi ¤ y, xi ¤ x}.

For any saturated chain x = z0 z1 · · · zk = y, there is some i for which

˜ ˜ ˜

xj ¤ zi and xj ¤ zi+1 . Hence »(zi , zi+1 ) = j. Thus if »(z0 , z1 ) ≥ · · · ≥ »(zk’1 , zk ),

˜

then »(z0 , z1 ) = j. Moreover, there is a unique y1 satisfying x = x0 y1 ¤ y and

˜

»(x0 , y1 ) = j, viz., y1 = x0 ∨ xj . (Note that y1 x0 by semimodularity.)

46 R. STANLEY, HYPERPLANE ARRANGEMENTS

By the induction hypothesis there exists a unique saturated chain y1 y2

˜ ˜ ˜ ˜

· · · yk = y satisfying »(y1 , y2 ) ≥ · · · ≥ »(yk’1 , yk ). Since »(y0 , y1 ) = j > »(y1 , y2 ),

the proof of Claim 1 follows by induction.

Claim 2. The broken circuit complex BC(M ) consists of all chain labels »(C),

˜

where C is a saturated increasing chain (with respect to ») from ˆ to some x ∈ 0

L(M ). Moreover, all such »(C) are distinct.

To prove the distinctness of the labels »(C), suppose that C is given by ˆ = 0

˜

y0 y1 · · · yk , with »(C) = (a1 , a2 , . . . , ak ). Then yi = yi’1 ∨ xai , so C is the

only chain with its label.

˜

Now let C and »(C) be as in the previous paragraph. We claim that the

set {xa1 , . . . , xak } contains no broken circuit. (We don™t even require that C is

increasing for this part of the proof.) Write zi = xai , and suppose to the contrary

that B = {zi1 , . . . , zij } is a broken circuit, with 1 ¤ i1 < · · · < ij ¤ k. Let B ∪ {xr }

be a circuit with r > ait for 1 ¤ t ¤ j. Now for any circuit {u1 , . . . , uh } and any

1 ¤ i ¤ h we have

u1 ∨ u2 ∨ · · · ∨ uh = u1 ∨ · · · ∨ ui’1 ∨ ui+1 ∨ · · · ∨ uh .

Thus

zi1 ∨ zi2 ∨ · · · ∨ zij’1 ∨ xr = z = z i1 ∨ z i2 ∨ · · · ∨ z ij .

z∈B

Then yij ’1 ∨ xr = yij , contradicting the maximality of the label aij . Hence

{xa1 , . . . , xak } ∈ BC(M ).

Conversely, suppose that T := {xa1 , . . . , xak } contains no broken circuit, with

a1 < · · · < ak . Let yi = xa1 ∨ · · · ∨ xai , and let C be the chain ˆ := y0 y1 · · · yk .

0

˜

(Note that C is saturated by semimodularity.) We claim that »(C) = (a1 , . . . , ak ).

If not, then yi’1 ∨ xj = yi for some j > ai . Thus

rk(T ) = rk(T ∪ {xj }) = i.

Since T is independent, T ∪ {xj } contains a circuit Q satisfying xj ∈ Q, so T

contains a broken circuit. This contradiction completes the proof of Claim 2.

To complete the proof of the theorem, note that we have shown that fi’1 (BC(M ))

˜

is the number of chains C : ˆ = y0 y1 · · · yi such that »(C) is strictly increas-

0

ing, or equivalently, »(C) is strictly decreasing. Since » is an E-labeling, the proof

follows from Theorem 4.11.

Corollary 4.6. The broken circuit complex BC(M ) is pure, i.e., every maximal