(9) [2+] Generalize the previous exercise as follows. Let G be a doubly-connected

graph with lattice of contractions LG . Let π ∈ LG . Show that the following two

conditions are equivalent.

(a) π is a modular element of LG .

(b) π satis¬es the following two properties:

(i) At most one block B of π contains more than one vertex of G.

(ii) Let H be the subgraph induced by the block B of (i). Let K be any

connected component of the subgraph induced by G ’ B, and let H1

be the graph induced by the set of vertices in H that are connected

to some vertex in K. Then H1 is a clique (complete subgraph) of G.

[2+] Let L be a geometric lattice of rank n, and ¬x x ∈ L. Show that

(10)

µ(y)χLy (t)tn’rk(x∨y) ,

χL (t) =

y∈L

x§y=ˆ0

ˆ

where Ly is the image of the interval [0, x] under the map z ’ z ∨ y.

(11) [2+] Let I(M ) be the set of independent sets of a matroid M . Find another

matroid N and a labeling of its points for which I(M ) = BCr (N ), the reduced

broken circuit complex of N .

LECTURE 4. BROKEN CIRCUITS AND MODULAR ELEMENTS 59

(12) (a) [2+] If ∆ and “ are simplicial complexes on disjoint sets A and B, respec-

tively, then de¬ne the join ∆ — “ to be the simplicial complex on the set

A ∪ B with faces F ∪ G, where F ∈ ∆ and G ∈ “. (E.g., if “ consists of

a single point then ∆ — “ is the cone over ∆. If “ consists of two disjoint

points, then ∆ — “ is the suspension of ∆.) We say that ∆ and “ are join-

factors of ∆ — “. Now let M be a matroid and S ‚ M a modular ¬‚at, i.e., S

is a modular element of LM . Order the points of M such that if p ∈ S and

q ∈ S, then p < q. Show that BC(S) is a join-factor of BC(M ). Deduce

that χM (t) is divisible by χS (t).

(b) [2+] Conversely, let M be a matroid and S ‚ M . Label the points of M so

that if p ∈ S and q ∈ S, then p < q. Suppose that BC(S) is a join-factor of

BC(M ). Show that S is modular.

(13) [2] Do Exercise 7, this time using Theorem 4.12 (the Broken Circuit Theorem).

(14) [1] Show that all geometric lattices of rank two are supersolvable.

(15) [2] Give an example of two nonisomorphic supersolvable geometric lattices of

rank 3 with the same characteristic polynomials.

(16) [2] Prove Proposition 4.11: if G is a graph with blocks G1 , . . . , Gk , then LG ∼

=

LG1 — · · · — L Gk .

(17) [2+] Give an example of a nonsupersolvable geometric lattice of rank three whose

characteristic polynomial has only integer zeros.

(18) [2] Let L1 and L2 be geometric lattices. Show that L1 and L2 are supersolvable

if and only if L1 — L2 is supersolvable.

(19) [3“] Let L be a supersolvable geometric lattice. Show that every interval of L is

also supersolvable.

(20) [2] (a) Find the number of maximal chains of the partition lattice Πn .

(b) Find the number of modular maximal chains of Πn .

(21) Let M be a matroid with a linear ordering of its points. The internal activity of

a basis B is the number of points p ∈ B such that p < q for all points q = p not

in the closure B ’ p of B ’ p. The external activity of B is the number of points

p ∈ M ’ B such that p < q for all q = p contained in the unique circuit that

is a subset of B ∪ {p }. De¬ne the Crapo beta invariant of M by

β(M ) = (’1)rk(M )’1 χ M (1),

where denotes di¬erentiation.

(a) [1+] Show that 1’χ M (1) = ψ(BCr ), the Euler characteristic of the reduced

broken circuit complex of M .

(b) [3“] Show that β(M ) is equal to the number of bases of M with internal

activity 0 and external activity 0.

(c) [2] Let A be a real central arrangement with associated matroid MA . Sup-

pose that A = cA for some arrangement A , where cA denotes the cone

over A . Show that β(MA ) = b(A ).

(d) [2+] With A as in (c), let H be a (proper) translate of some hyperplane

H ∈ A. Show that β(MA ) = b(A ∪ {H }).

LECTURE 5

Finite ¬elds

5.1. The ¬nite ¬eld method

In this lecture we will describe a method based on ¬nite ¬elds for computing the

characteristic polynomial of an arrangement de¬ned over Q. We will then discuss

several interesting examples. The main result (Theorem 5.15) is implicit in the

work of Crapo and Rota [9, §17]. It was ¬rst developed into a systematic tool for

computing characteristic polynomials by Athanasiadis [1][2], after a closely related

but not as general technique was presented by Blass and Sagan [6].

Suppose that the arrangement A is de¬ned over Q. By multiplying each hyper-

plane equation by a suitable integer, we may assume A is de¬ned over Z. In that

case we can take coe¬cients modulo a prime p and get an arrangement Aq de¬ned

over the ¬nite ¬eld Fq , where q = pr . We say that A has good reduction mod p (or

over Fq ) if L(A) ∼ L(Aq ).

=

For instance, let A be the a¬ne arrangement in Q1 = Q consisting of the points

0 and 10. Then L(A) contains three elements, viz., Q, {0}, and {10}. If p = 2, 5

then 0 and 10 remain distinct, so A has good reduction. On the other hand, if

p = 2 or p = 5 then 0 = 10 in Fp , so L(Ap ) contains just two elements. Hence A

has bad reduction when p = 2, 5.

Proposition 5.13. Let A be an arrangement de¬ned over Z. Then A has good

reduction for all but ¬nitely many primes p.

Proof. Let H1 , . . . , Hj be a¬ne hyperplanes, where Hi is given by the equation

vi · x = ai (vi , ai ∈ Zn ). By linear algebra, we have H1 © · · · © Hj = … if and only if

® ®

v1 a1 v1

. . = rank . .

rank ° . .» °.»

(36) . . .

vj aj vj

Moreover, if (36) holds then

®

v1

.

dim(H1 © · · · © Hj ) = n ’ rank ° . » .

.

vj

61

62 R. STANLEY, HYPERPLANE ARRANGEMENTS

Now for any r — s matrix A, we have rank(A) ≥ t if and only if some t — t submatrix

B satis¬es det(B) = 0. It follows that L(A) ∼ L(Ap ) if and only if at least one

=

member S of a certain ¬nite collection S of subsets of integer matrices B satis¬es

the following condition:

(∀B ∈ S) det(B) = 0 but det(B) ≡ 0 (mod p).

This can only happen for ¬nitely many p, viz., for certain B we must have p| det(B),

so L(A) ∼ L(Ap ) for p su¬ciently large.

=

The main result of this section is the following. Like many fundamental results

in combinatorics, the proof is easy but the applicability very broad.

Theorem 5.15. Let A be an arrangement in Qn , and suppose that L(A) ∼ L(Aq )

=

for some prime power q. Then

«

χA (q) = # Fn ’ H

q

H∈Aq

= qn ’ # H.

H∈Aq

Proof. Let x ∈ L(Aq ) so #x = q dim(x) . Here dim(x) can be computed either over

Q or Fq . De¬ne two functions f, g : L(Aq ) ’ Z by

f (x) = #x

= # x’

g(x) y .

y>x

In particular,

«

g(ˆ = g(Fn ) = # Fn ’ H .

0) q q

H∈Aq

Clearly