Theorem 3.8. Let L be a ¬nite lattice. The following two conditions are equivalent.

(1) L is a geometric lattice.

(2) L ∼ L(M ) for some (simple) matroid M .

=

Proof. Assume that L is geometric, and let A be the set of atoms of L. If T ⊆ A

then write T = x∈T x, the join of all elements of T . Let

I = {I ⊆ A : rk(∨I) = #I}.

Note that by semimodularity, we have for any S ⊆ A and x ∈ A that rk(( S)∨x) ¤

rk( S) + 1. (Hence in particular, rk( S) ¤ #S.) It follows that I is a simplicial

complex. Let S ⊆ A, and let T, T be maximal elements of 2S © I. We need to show

that #T = #T .

Assume #T < #T , say. If y ∈ S then y ¤ T , else T = T ∪ y satis¬es

rk( T ) = #T , contradicting the maximality of T . Since #T < #T and T ⊆ S,

it follows that T < T [why?]. Since L is atomic, there exists y ∈ S such that

y ∈ S but y ¤ T . But then rk( (T ∪ y)) = 1 + #T , contradicting the maximality

of T . Hence M = (A, I) is a matroid, and L ∼ L(M ).

=

Conversely, given a matroid M , which we may assume is simple, we need to

show that L(M ) is a geometric lattice. Clearly L(M ) is atomic, since every ¬‚at is

the join of its elements. Let S, T ⊆ M . We will show that

rk(S) + rk(T ) ≥ rk(S © T ) + rk(S ∪ T ).

(24)

LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 37

Note that if S and T are ¬‚ats (i.e., S, T ∈ L(M )) then S © T = S § T and

rk(S ∪ T ) = rk(S ∨ T ). Hence taking S and T to be ¬‚ats in (24) shows that L(M )

is semimodular and thus geometric. Suppose (24) is false, so

rk(S ∪ T ) > rk(S) + rk(T ) ’ rk(S © T ).

Let B be a basis for S ∪T extending a basis for S ∪T . Then either #(B ©S) > rk(S)

or #(B © T ) > rk(T ), a contradiction completing the proof.

Note that by Proposition 3.6 and Theorem 3.8, any results we prove about geo-

metric lattices hold a fortiori for the intersection lattice LA of a central arrangement

A.

Note. If L is geometric and x ¤ y in L, then it is easy to show using semi-

modularity that the interval [x, y] is also a geometric lattice. (See Exercise 3.) In

general, however, an interval of an atomic lattice need not be atomic.

For noncentral arrangements L(A) is not a lattice, but there is still a connection

with geometric lattices. For a stronger statement, see Exercise 4.

Proposition 3.8. Let A be an arrangement. Then every interval [x, y] of L(A) is

a geometric lattice.

Proof. By Exercise 3, it su¬ces to take x = ˆ Now [ˆ y] ∼ L(Ay ), where Ay is

0. 0, =

given by (6). Since Ay is a central arrangement, the proof follows from Proposi-

tion 3.6.

The proof of our next result about geometric lattices will use a fundamental

formula concerning M¨bius functions known as Weisner™s theorem. For a proof, see

o

[18, Cor. 3.9.3] (where it is stated in dual form).

Theorem 3.9. Let L be a ¬nite lattice with at least two elements and with M¨bius

o

ˆ = a ∈ L. Then

function µ. Let 0

(25) µ(x) = 0.

x : x∨a=ˆ

1

Note that Theorem 3.9 gives a “shortening” of the recurrence (2) de¬ning µ.

Normally we take a to be an atom, since that produces fewer terms in (25) than

choosing any b > a. As an example, let L = Bn , the boolean algebra of all subsets

of [n], and let a = {n}. There are two elements x ∈ Bn such that x ∨ a = ˆ = [n],

1

viz., x1 = [n ’ 1] and x2 = [n]. Hence µ(x1 ) + µ(x2 ) = 0. Since [ˆ x1 ] = Bn’1 and

0,

[ˆ x2 ] = Bn , we easily obtain µBn (ˆ = (’1) , agreeing with (4).

n

0, 1)

If x ¤ y in a graded lattice L, write rk(x, y) = rk(y) ’ rk(x), the length of

every saturated chain from x to y. The next result may be stated as “the M¨biuso

function of a geometric lattice strictly alternates in sign.”

Theorem 3.10. Let L be a ¬nite geometric lattice with M¨bius function µ, and let

o

x ¤ y in L. Then

(’1)rk(x,y) µ(x, y) > 0.

Proof. Since every interval of a geometric lattice is a geometric lattice (Exercise 3),

it su¬ces to prove the theorem for [x, y] = [ˆ ˆ The proof is by induction on the

0, 1].

rank of L. It is clear if rk(L) = 1, in which case µ(ˆ ˆ = ’1. Assume the result

0, 1)

for geometric lattices of rank < n, and let rk(L) = n. Let a be an atom of L in

Theorem 3.9. For any y ∈ L we have by semimodularity that

rk(y § a) + rk(y ∨ a) ¤ rk(y) + rk(a) = rk(y) + 1.

38 R. STANLEY, HYPERPLANE ARRANGEMENTS

Hence x ∨ a = ˆ if and only if x = ˆ or x is a coatom (i.e., x ˆ satisfying a ¤ x.

1 1 1)

From Theorem 3.9 there follows

µ(ˆ ˆ = ’ µ(ˆ x).

0, 1) 0,

a¤x ˆ

1

The sum on the right is nonempty since L is atomic, and by induction every x

indexing the sum satis¬es (’1)n’1 µ(ˆ x) > 0. Hence (’1)n µ(ˆ ˆ > 0.

0, 0, 1)

Combining Proposition 3.8 and Theorem 3.10 yields the following result.

Corollary 3.4. Let A be any arrangement and x ¤ y in L(A). Then

(’1)rk(x,y) µ(x, y) > 0,

where µ denotes the M¨bius function of L(A).

o

Similarly, combining Theorem 3.10 with the de¬nition (22) of χM (t) gives the

next corollary.

Corollary 3.5. Let M be a matroid of rank n. Then the characteristic polynomial

χM (t) strictly alternates in sign, i.e., if

χM (t) = an tn + an’1 tn’1 + · · · + a0 ,

then (’1)n’i ai > 0 for 0 ¤ i ¤ n.

Let A be an n-dimensional arrangement of rank r. If MA is the matroid

corresponding to A, as de¬ned in Proposition 3.6, then

χA (t) = tn’r χM (t).

(26)

It follows from Corollary 3.5 and equation (26) that we can write

χA (t) = bn tn + bn’1 tn’1 + · · · + bn’r tn’r ,

where (’1)n’i bi > 0 for n ’ r ¤ i ¤ n.

LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 39

Exercises

(1) (a) [1+] Let χG (t) be the characteristic polynomial of the graphical arrange-

ment AG . Suppose that χG (i) = 0, where i ∈ Z, i > 1. Show that

χG (i ’ 1) = 0.

(b) [2] Is the same conclusion true for any central arrangement A?

(2) [2] Show that if F and F are ¬‚ats of a matroid M , then so is F © F .

(3) [2] Prove the assertion in the Note following the proof of Theorem 3.8 that an

interval [x, y] of a geometric lattice L is also a geometric lattice.

(4) [2+] Let A be an arrangement (not necessarily central). Show that there exists

a geometric lattice L and an atom a of L such that L(A) ∼ L ’ Va , where

=

Va = {x ∈ L : x ≥ a}.

(5) [2“] Let L be a geometric lattice of rank n, and de¬ne the truncation T (L) to

be the subposet of L consisting of all elements of rank = n ’ 1. Show that T (L)

is a geometric lattice.

(6) Let Wi be the number of elements of rank i in a geometric lattice (or just in the

intersection poset of a central hyperplane arrangement, if you prefer) of rank n.

(a) [3] Show that for k ¤ n/2,

W1 + W2 + · · · + Wk ¤ Wn’k + Wn’k+1 + · · · + Wn’1 .

(b) [2“] Deduce from (a) and Exercise 5 that W1 ¤ Wk for all 1 ¤ k ¤ n ’ 1.

(c) [5] Show that Wi ¤ Wn’i for i < n/2 and that the sequence W0 , W1 , . . . , Wn

is unimodal. (Compare Lecture 2, Exercise 9.)

(7) [3“] Let x ¤ y in a geometric lattice L. Show that µ(x, y) = ±1 if and only if

the interval [x, y] is isomorphic to a boolean algebra. (Use Weisner™s theorem.)

Note. This problem becomes much easier using Theorem 4.12 (the Broken

Circuit Theorem); see Exercise 13.

LECTURE 4

Broken circuits, modular elements, and supersolvability

This lecture is concerned primarily with matroids and geometric lattices. Since

the intersection lattice of a central arrangement is a geometric lattice, all our results

can be applied to arrangements.

4.1. Broken circuits

For any geometric lattice L and x ¤ y in L, we have seen (Theorem 3.10) that