100 101 001

Let us now de¬ne a number of important terms associated to a matroid M .

A basis of M is a maximal independent set. A circuit C is a minimal dependent

set, i.e., C is not independent but becomes independent when we remove any point

from it. For example, the circuits of the matroid of Figure 1 are 123, 345, and 1245.

If M = (S, I) is a matroid and T ⊆ S then de¬ne the rank rk(T ) of T by

rk(T ) = max{#I : I ∈ I and I ⊆ T }.

In particular, rk(…) = 0. We de¬ne the rank of the matroid M itself by rk(M ) =

rk(S). A k-¬‚at is a maximal subset of rank k. For instance, if M is an a¬ne

matroid, i.e., if S is a subset of an a¬ne space and independence in M is given by

a¬ne independence, then the ¬‚ats of M are just the intersections of S with a¬ne

subspaces. Note that if F and F are ¬‚ats of a matroid M , then so is F © F (see

Exercise 2). Since the intersection of ¬‚ats is a ¬‚at, we can de¬ne the closure T of

a subset T ⊆ S to be the smallest ¬‚at containing T , i.e.,

T= F.

¬‚ats F ⊇T

This closure operator has a number of nice properties, such as T = T and T ⊆

T ’ T ⊆ T.

3.2. The lattice of ¬‚ats and geometric lattices

For a matroid M de¬ne L(M ) to be the poset of ¬‚ats of M , ordered by inclusion.

Since the intersection of ¬‚ats is a ¬‚at, L(M ) is a meet-semilattice; and since L(M )

has a top element S, it follows from Lemma 2.3 that L(M ) is a lattice, which we

call the lattice of ¬‚ats of M . Note that L(M ) has a unique minimal element ˆ viz.,

0,

¯ or equivalently, the intersection of all ¬‚ats. It is easy to see that L(M ) is graded

…

by rank, i.e., every maximal chain of L(M ) has length m = rk(M ). Thus if x y in

34 R. STANLEY, HYPERPLANE ARRANGEMENTS

1 5

2 4

3

Figure 2. The lattice of ¬‚ats of the matroid of Figure 1

L(M ) then rk(y) = 1 + rk(x). We now de¬ne the characteristic polynomial χ M (t),

in analogy to the de¬nition (3) of χA (t), by

µ(ˆ x)tm’rk(x) ,

(22) χM (t) = 0,

x∈L(M )

where µ denotes the M¨bius function of L(M ) and m = rk(M ). Figure 2 shows the

o

lattice of ¬‚ats of the matroid M of Figure 1. From this ¬gure we see easily that

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

Let M be a matroid and x ∈ M . If the set {x} is dependent (i.e., if rk({x}) = 0)

then we call x a loop. Thus ¯ is just the set of loops of M . Suppose that x, y ∈ M ,

…

neither x nor y are loops, and rk({x, y}) = 1. We then call x and y parallel points.

A matroid is simple if it has no loops or pairs of parallel points. It is clear that the

following three conditions are equivalent:

• M is simple.

• ¯ = … and x = x for all x ∈ M .

… ¯

• rk({x, y}) = 2 for all points x = y of M (assuming M has at least two

points).

For any matroid M and x, y ∈ M , de¬ne x ∼ y if x = y . It is easy to see that ∼ is

¯¯

an equivalence relation. Let

M = {¯ : x ∈ M, x ∈ ¯

…},

(23) x

with an obvious de¬nition of independence, i.e.,

{¯1 , . . . , xk } ∈ I(M ) ” {x1 , . . . , xk } ∈ I(M ).

x ¯

Then M is simple, and L(M ) ∼ L(M). Thus insofar as intersection lattices L(M )

=

are concerned, we may assume that M is simple. (Readers familiar with point set

topology will recognize the similarity between the conditions for a matroid to be

simple and for a topological space to be T0 .)

Example 3.8. Let S be any ¬nite set and V a vector space. If f : S ’ V , then

de¬ne a matroid Mf on S by the condition that given I ⊆ S,

I ∈ I(M ) ” {f (x) : x ∈ I} is linearly independent.

LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 35

Then a loop is any element x satisfying f (x) = 0, and x ∼ y if and only if f (x) is

a nonzero scalar multiple of f (y).

Note. If M = (S, I) is simple, then L(M ) determines M . For we can identify

S with the set of atoms of L(M ), and we have

{x1 , . . . , xk } ∈ I ” rk(x1 ∨ · · · ∨ xk ) = k in L(M ).

See the proof of Theorem 3.8 for further details.

We now come to the primary connection between hyperplane arrangements and

matroid theory. If H is a hyperplane, write nH for some (nonzero) normal vector

to H.

Proposition 3.6. Let A be a central arrangement in the vector space V . De¬ne

a matroid M = MA on A by letting B ∈ I(M ) if B is linearly independent (i.e.,

{nH : H ∈ B} is linearly independent). Then M is simple and L(M ) ∼ L(A).

=

Proof. M has no loops, since every H ∈ A has a nonzero normal. Two distinct

nonparallel hyperplanes have linearly independent normals, so the points of M are

closed. Hence M is simple.

Let B, B ⊆ A, and set

X= H = XB , X = H = XB .

H∈B H∈B

Then X = X if and only if

span{nH : H ∈ B} = span{nH : H ∈ B }.

Now the closure relation in M is given by

B = {H ∈ A : nH ∈ span{nH : H ∈ B}}.

Hence X = X if and only if B = B , so L(M ) ∼ L(A).

=

It follows that for a central arrangement A, L(A) depends only on the matroidal

structure of A, i.e., which subsets of hyperplanes are linearly independent. Thus

the matroid MA encapsulates the essential information about A needed to de¬ne

L(A).

Our next goal is to characterize those lattices L which have the form L(M ) for

some matroid M .

Proposition 3.7. Let L be a ¬nite graded lattice. The following two conditions

are equivalent.

(1) For all x, y ∈ L, we have rk(x) + rk(y) ≥ rk(x § y) + rk(x ∨ y).

(2) If x and y both cover x § y, then x ∨ y covers both x and y.

Proof. Assume (1). Let x, y x § y, so rk(x) = rk(y) = rk(x § y) + 1 and

rk(x ∨ y) > rk(x) = rk(y). By (1),

rk(x) + rk(y) ≥ (rk(x) ’ 1) + rk(x ∨ y)

’ rk(y) ≥ rk(x ∨ y) ’ 1

’x∨y x.

Similarly x ∨ y y, proving (2).

For (2)’(1), see [18, Prop. 3.3.2].

36 R. STANLEY, HYPERPLANE ARRANGEMENTS

(a) (b) (c)

Figure 3. Three nongeometric lattices

De¬nition 3.9. A ¬nite lattice L satisfying condition (1) or (2) above is called

(upper) semimodular. A ¬nite lattice L is atomic if every x ∈ L is a join of atoms

(where we regard ˆ as an empty join of atoms). Equivalently, if x ∈ L is join-

0

irreducible (i.e., covers a unique element), then x is an atom. Finally, a ¬nite

lattice is geometric if it is both semimodular and atomic.

To illustrate these de¬nitions, Figure 3(a) shows an atomic lattice that is not

semimodular, (b) shows a semimodular lattice that is not atomic, and (c) shows a

graded lattice that is neither semimodular nor atomic.