has a direct combinatorial interpretation. To this end, let M be a matroid on the

set S = {u1 , . . . , um }. Linearly order the elements of S, say u1 < u2 < · · · < um .

Recall that a circuit of M is a minimal dependent subset of S.

De¬nition 4.10. A broken circuit of M (with respect to the linear ordering O of

S) is a set C ’ {u}, where C is a circuit and u is the largest element of C (in the

ordering O). The broken circuit complex BCO (M ) (or just BC(M ) if no confusion

will arise) is de¬ned by

BC(M ) = {T ⊆ S : T contains no broken circuit}.

Figure 1 shows two linear orderings O and O of the points of the a¬ne matroid

M of Figure 1 (where the ordering of the points is 1 < 2 < 3 < 4 < 5). With respect

to the ¬rst ordering O the circuits are 123, 345, 1245, and the broken circuits are

12, 34, 124. With respect to the second ordering O the circuits are 123, 145, 2345,

and the broken circuits are 12, 14, 234.

It is clear that the broken circuit complex BC(M ) is an abstract simplicial

complex, i.e., if T ∈ BC(M ) and U ⊆ T , then U ∈ BC(M ). In Figure 1 we

1 5 3 5

2 2

4 4

3 1

Figure 1. Two linear orderings of the matroid M of Figure 1

41

42 R. STANLEY, HYPERPLANE ARRANGEMENTS

have BCO (M ) = 135, 145, 235, 245 , while BCO (M ) = 135, 235, 245, 345 . These

simplicial complexes have geometric realizations as follows:

2

1 3

1

5 5

4 2 4 3

Note that the two simplicial complexes BCO (M ) and BCO (M ) are not iso-

morphic (as abstract simplicial complexes); in fact, their geometric realizations are

not even homeomorphic. On the other hand, if fi (∆) denotes the number of i-

dimensional faces (or faces of cardinality i ’ 1) of the abstract simplicial complex

∆, then for ∆ given by either BCO (M ) or BCO (M ) we have

f’1 (∆) = 1, f0 (∆) = 5, f1 (∆) = 8, f2 (∆) = 4.

Note, moreover, that

χM (t) = t3 ’ 5t2 + 8t ’ 4.

In order to generalize this observation to arbitrary matroids, we need to introduce

a fair amount of machinery, much of it of interest for its own sake. First we give

a fundamental formula, known as Philip Hall™s theorem, for the M¨bius function

o

ˆˆ

value µ(0, 1).

Lemma 4.4. Let P be a ¬nite poset with ˆ and ˆ and with M¨bius function µ.

0 1, o

ˆ = y0 < y1 < · · · < yi = ˆ in P . Then

Let ci denote the number of chains 0 1

µ(ˆ ˆ = ’c1 + c2 ’ c3 + · · · .

0, 1)

Proof. We work in the incidence algebra I(P ). We have

µ(ˆ ˆ = ζ ’1 (ˆ ˆ

0, 1) 0, 1)

= (δ + (ζ ’ δ))’1 (ˆ ˆ

0, 1)

= δ(ˆ ˆ ’ (ζ ’ δ)(ˆ ˆ + (ζ ’ δ)2 (ˆ ˆ ’ · · · .

0, 1) 0, 1) 0, 1)

This expansion is easily justi¬ed since (ζ ’δ)k (0, ˆ = 0 if the longest chain of P has

ˆ 1)

length less than k. By de¬nition of the product in I(P ) we have (ζ ’ δ)i (ˆ ˆ = ci ,

0, 1)

and the proof follows.

Note. Let P be a ¬nite poset with ˆ and ˆ and let P = P ’ {ˆ ˆ De¬ne

0 1, 0, 1}.

∆(P ) to be the set of chains of P , so ∆(P ) is an abstract simplicial complex. The

reduced Euler characteristic of a simplicial complex ∆ is de¬ned by

χ(P ) = ’f’1 + f0 ’ f1 + · · · ,

˜

where fi is the number of i-dimensional faces F ∈ ∆ (or #F = i + 1). Comparing

with Lemma 4.4 shows that

µ(ˆ ˆ = χ(∆(P )).

0, 1) ˜

Readers familiar with topology will know that χ(∆) has important topological sig-

˜

ni¬cance related to the homology of ∆. It is thus natural to ask whether results

LECTURE 4. BROKEN CIRCUITS AND MODULAR ELEMENTS 43

1

32

1 1 2 1

1 1

213 1 2

3

2 2

1 2 3

1 3 1 2

12 3

(a) (b) (c)

Figure 2. Three examples of edge-labelings

concerning M¨bius functions can be generalized or re¬ned topologically. Such re-

o

sults are part of the subject of “topological combinatorics,” about which we will

say a little more later.

Now let P be a ¬nite graded poset with ˆ and ˆ Let

0 1.

E(P ) = {(x, y) : x y in P },

the set of (directed) edges of the Hasse diagram of P .

De¬nition 4.11. An E-labeling of P is a map » : E(P ) ’ P such that if x < y in

P then there exists a unique saturated chain

···

C : x = x0 x1 x1 xk = y

satisfying

»(x0 , x1 ) ¤ »(x1 , x2 ) ¤ · · · ¤ »(xk’1 , xk ).

We call C the increasing chain from x to y.

Figure 2 shows three examples of posets P with a labeling of their edges, i.e.

a map » : E(P ) ’ P. Figure 2(a) is the boolean algebra B3 with the labeling

»(S, S ∪ {i}) = i. (The one-element subsets {i} are also labelled with a small

i.) For any boolean algebra Bn , this labeling is the archetypal example of an E-

labeling. The unique increasing chain from S to T is obtained by adjoining to S

the elements of T ’ S one at a time in increasing order. Figures 2(b) and (c) show

two di¬erent E-labelings of the same poset P . These labelings have a number of

di¬erent properties, e.g., the ¬rst has a chain whose edge labels are not all di¬erent,

while every maximal chain label of Figure 2(c) is a permutation of {1, 2}.

Theorem 4.11. Let » be an E-labeling of P , and let x ¤ y in P . Let µ denote

the M¨bius function of P . Then (’1)rk(x,y) µ(x, y) is equal to the number of strictly

o

decreasing saturated chains from x to y, i.e.,

(’1)rk(x,y) µ(x, y) =

··· xk = y : »(x0 , x1 ) > »(x1 , x2 ) > · · · > »(xk’1 , xk )}.

#{x = x0 x1

Proof. Since » restricted to [x, y] (i.e., to E([x, y])) is an E-labeling, we can assume

[x, y] = [ˆ ˆ = P . Let S = {a1 , a2 , . . . , aj’1 } ⊆ [n ’ 1], with a1 < a2 < · · · < aj’1 .

0, 1]

44 R. STANLEY, HYPERPLANE ARRANGEMENTS

De¬ne ±P (S) to be the number of chains ˆ < y1 < · · · < yj’1 < ˆ in P such that

0 1

rk(yi ) = ai for 1 ¤ i ¤ j ’ 1. The function ±P is called the ¬‚ag f -vector of P .

Claim. ±P (S) is the number of maximal chains ˆ = x0 x1 · · · xn = ˆ such

0 1

that

»(xi’1 , xi ) > »(xi , xi+1 ) ’ i ∈ S, 1 ¤ i ¤ n.

(27)