0 1,

exactly one nonsingleton block Bi (necessarily with i + 1 elements), with

B1 ‚ B2 · · · ‚ Bn’1 = [n]. In particular, Πn is supersolvable and has

exactly n!/2 modular chains for n > 1. The atoms covered by πi are the

partitions with one nonsingleton block {j, k} ⊆ Bi . Hence πi lies above

exactly i+1 atoms, so

2

i+1 i

’

ei = = i.

2 2

It follows that χΠn (t) = (t ’ 1)(t ’ 2) · · · (t ’ n + 1) and µΠn (ˆ =

1)

n’1

(n ’ 1)!. Compare Corollary 2.2. The polynomials χBn (t) and

(’1)

χΠn (t) di¬er by a factor of t because Bn (t) is an arrangement in K n of

LECTURE 4. BROKEN CIRCUITS AND MODULAR ELEMENTS 55

rank n ’ 1. In general, if A is an arrangement and ess(A) its essentializa-

tion, then

trk(ess(A)) χA (t) = trk(A) χess(A) (t).

(35)

(See Lecture 1, Exercise 2.)

Note. It is natural to ask whether there is a more general class of geometric

lattices L than the supersolvable ones for which χL (t) factors into linear factors

(over Z). There is a profound such generalization due to Terao [22] when L is an

intersection poset of a linear arrangement A in K n . Write K[x] = K[x1 , . . . , xn ]

and de¬ne

T(A) = {(p1 , . . . , pn ) ∈ K[x]n : pi (H) ⊆ H for all H ∈ A}.

Here we are regarding (p1 , . . . , pn ) : K n ’ K n , viz., if (a1 , . . . , an ) ∈ K n , then

(p1 , . . . , pn )(a1 , . . . , an ) = (p1 (a1 , . . . , an ), . . . , pn (a1 , . . . , an )).

The K[x]-module structure K[x] — T(A) ’ T(A) is given explicitly by

q · (p1 , . . . , pn ) = (qp1 , . . . , qpn ).

Note, for instance, that we always have (x1 , . . . , xn ) ∈ T(A). Since A is a linear

arrangement, T(A) is indeed a K[x]-module. (We have given the most intuitive

de¬nition of the module T(A), though it isn™t the most useful de¬nition for proofs.)

It is easy to see that T(A) has rank n as a K[x]-module, i.e., T(A) contains n,

but not n + 1, elements that are linearly independent over K[x]. We say that A

is a free arrangement if T(A) is a free K[x]-module, i.e., there exist Q1 , . . . , Qn ∈

T(A) such that every element Q ∈ T(A) can be uniquely written in the form

Q = q1 Q1 + · · · + qn Qn , where qi ∈ K[x]. It is easy to see that if T(A) is free,

then the basis {Q1 , . . . , Qn } can be chosen to be homogeneous, i.e., all coordinates

of each Qi are homogeneous polynomials of the same degree di . We then write

di = deg Qi . It can be shown that supersolvable arrangements are free, but there

are also nonsupersolvable free arrangements. The property of freeness seems quite

subtle; indeed, it is unknown whether freeness is a matroidal property, i.e., depends

only on the intersection lattice LA (regarding the ground ¬eld K as ¬xed). The

remarkable “factorization theorem” of Terao is the following.

Theorem 4.14. Suppose that T(A) is free with homogeneous basis Q1 , . . . , Qn . If

deg Qi = di then

χA (t) = (t ’ d1 )(t ’ d2 ) · · · (t ’ dn ).

We will not prove Theorem 4.14 here. A good reference for this subject is [13,

Ch. 4].

Returning to supersolvability, we can try to characterize the supersolvable prop-

erty for various classes of geometric lattices. Let us consider the case of the bond

lattice LG of the graph G. A graph H with at least one edge is doubly connected if

it is connected and remains connected upon the removal of any vertex (and all in-

cident edges). A maximal doubly connected subgraph of a graph G is called a block

of G. For instance, if G is a forest then its blocks are its edges. Two di¬erent blocks

of G intersect in at most one vertex. Figure 5 shows a graph with eight blocks, ¬ve

of which consist of a single edge. The following proposition is straightforward to

prove (Exercise 16).

56 R. STANLEY, HYPERPLANE ARRANGEMENTS

Figure 5. A graph with eight blocks

Proposition 4.11. Let G be a graph with blocks G1 , . . . , Gk . Then

LG ∼ LG — · · · — L G .

= k

1

It is also easy to see that if L1 and L2 are geometric lattices, then L1 and

L2 are supersolvable if and only if L1 — L2 is supersolvable (Exercise 18). Hence

in characterizing supersolvable graphs G (i.e., graphs whose bond lattice L G is

supersolvable) we may assume that G is doubly connected. Note that for any

connected (and hence a fortiori doubly connected) graph G, any coatom π of LG

has exactly two blocks.

Proposition 4.12. Let G be a doubly connected graph, and let π = {A, B} be a

coatom of the bond lattice LG , where #A ¤ #B. Then π is a modular element of

LG if and only if #A = 1, say A = {v}, and the neighborhood N (v) (the set of

vertices adjacent to v) forms a clique (i.e., any two distinct vertices of N (v) are

adjacent).

Proof. The proof parallels that of Proposition 4.9, which is a special case. Suppose

that #A > 1. Since G is doubly connected, there exist u, v ∈ A and u , v ∈ B such

that u = v, u = v , uu ∈ E(G), and vv ∈ E(G). Set σ = {(A∪u )’v, (B∪v)’u }.

If G has n vertices then rk(π) = rk(σ) = n’2, rk(π∨σ) = n’1, and rk(π§σ) = n’4.

Hence π is not modular.

Assume then that A = {v}. Suppose that av, bv ∈ E(G) but ab ∈ E(G). We

need to show that π is not modular. Let σ = {A ’ {a, b}, {a, b, v}}. Then

σ∨π =ˆ σ § π = {A ’ {a, b}, a, b, v}

1,

rk(σ) = rk(π) = n ’ 2, rk(σ ∨ π) = n ’ 1, rk(σ § π) = n ’ 4.

Hence π is not modular.

Conversely, let π = {A, v}. Assume that if av, bv ∈ E(G) then ab ∈ E(G).

It is then straightforward to show (Exercise 8) that π is modular, completing the

proof.

As an immediate consequence of Propositions 4.10(b) and 4.12 we obtain a

characterization of supersolvable graphs.

Corollary 4.10. A graph G is supersolvable if and only if there exists an ordering

v1 , v2 , . . . , vn of its vertices such that if i < k, j < k, vi vk ∈ E(G) and vj vk ∈ E(G),

LECTURE 4. BROKEN CIRCUITS AND MODULAR ELEMENTS 57

then vi vj ∈ E(G). Equivalently, in the restriction of G to the vertices v1 , v2 , . . . , vi ,

the neighborhood of vi is a clique.

Note. Supersolvable graphs G had appeared earlier in the literature under the

names chordal, rigid circuit, or triangulated graphs. One of their many characteri-

zations is that any circuit of length at least four contains a chord. Equivalently, no

induced subgraph of G is a k-cycle for k ≥ 4.

58 R. STANLEY, HYPERPLANE ARRANGEMENTS

Exercises

(1) [2“] Let M be a matroid on a linearly ordered set. Show that BC(M ) = BC(M ),

where M is de¬ned by equation (23).

(2) [2+] Let M be a matroid of rank at least one. Show that the coe¬cients of the

polynomial χM (t)/(t ’ 1) alternate in sign.

(3) (a) [2+] Let L be ¬nite lattice for which every element has a unique comple-

ment. Show that L is isomorphic to a boolean algebra Bn .

(b) [3] A lattice L is distributive if

x ∨ (y § z) = (x ∨ y) § (x ∨ z)

x § (y ∨ z) = (x § y) ∨ (x § z)

for all x, y, z ∈ L. Let L be an in¬nite lattice with ˆ and ˆ If every element

0 1.

of L has a unique complement, then is L a distributive lattice?

(4) [3“] Let x be an element of a geometric lattice L. Show that the following four

conditions are equivalent.

(i) x is a modular element of L.

(ii) If x § y = ˆ then

0,

rk(x) + rk(y) = rk(x ∨ y).

(iii) If x and y are complements, then rk(x) + rk(y) = n.

(iv) All complements of x are incomparable.

[2+] Let x, y be modular elements of a geometric lattice L. Show that x § y is

(5)

also modular.

(6) [2] Let L be a geometric lattice. Prove or disprove: if x is modular in L and y

is modular in the interval [x, ˆ then y is modular in L.

1],

(7) [2“] Let L and L be ¬nite lattices. Show that if both L and L are geometric

(respectively, atomic, semimodular, modular) lattices, then so is L — L .

[2] Let G be a (loopless) connected graph and v ∈ V (G). Let A = V (G) ’ v and

(8)

π = {A, v} ∈ LG . Suppose that whenever av, bv ∈ E(G) we have ab ∈ E(G).