(’1)e(F ) tn’e(F ) ,

χA# (t) =

G

F

where F ranges over all spanning forests of G.

30 R. STANLEY, HYPERPLANE ARRANGEMENTS

Exercises

(1) [3“] Show that for any arrangement A, we have χcA (t) = (t ’ 1)χA (t), where cA

denotes the cone over A. (Use Whitney™s theorem.)

(2) [2“] Let G be a graph on the vertex set [n]. Show that the bond lattice LG is a

sub-join-semilattice of the partition lattice Πn but is not in general a sublattice

of Πn .

(3) [2“] Let G be a forest (graph with no cycles) on the vertex set [n]. Show that

LG ∼ BE(G) , the boolean algebra of all subsets of E(G).

=

(4) [2] Let G be a graph with n vertices and AG the corresponding graphical ar-

rangement. Suppose that G has a k-element clique, i.e., k vertices such that any

two are adjacent. Show that k!|r(A).

(5) [2+] Let G be a graph on the vertex set [n] = {1, 2, . . . , n}, and let AG be the

corresponding graphical arrangement (over any ¬eld K, but you may assume

K = R if you wish). Let Cn be the coordinate hyperplane arrangement, con-

sisting of the hyperplanes xi = 0, 1 ¤ i ¤ n. Express χAG ∪Cn (t) in terms of

χAG (t).

(6) [4] Let G be a planar graph, i.e., G can be drawn in the plane without crossing

edges. Show that χAG (4) = 0.

(7) [2+] Let G be a graph with n vertices. Show directly from the the deletion-

contraction recurrence (20) that

(’1)n χG (’1) = #AO(G).

(8) [2+] Let χG (t) = tn ’ cn’1 tn’1 + · · · + (’1)n’1 c1 t be the chromatic polynomial

of the graph G. Let i be a vertex of G. Show that c1 is equal to the number of

acyclic orientations of G whose unique source is i. (A source is a vertex with no

arrows pointing in. In particular, an isolated vertex is a source.)

(9) [5] Let A be an arrangement with characteristic polynomial χA (t) = tn ’

cn’1 tn’1 + cn’2 tn’2 ’ · · · + (’1)n c0 . Show that the sequence c0 , c1 , . . . , cn = 1

is unimodal, i.e., for some j we have

c0 ¤ c1 ¤ · · · ¤ cj ≥ cj+1 ≥ · · · ≥ cn .

(10) [2+] Let f (n) be the total number of faces of the braid arrangement Bn . Find

a simple formula for the generating function

xn x2 x3 x4 x5 x6

= 1 + x + 3 + 13 + 75 + 541 + 4683 + · · · .

f (n)

n! 2! 3! 4! 5! 6!

n≥0

More generally, let fk (n) denote the number of k-dimensional faces of Bn . For

instance, f1 (n) = 1 (for n ≥ 1) and fn (n) = n!. Find a simple formula for the

generating function

n

x2 3

kx 3x

2 2

= 1 + yx + (y + 2y ) + (y + 6y + 6y ) + · · · .

fk (n)y

n! 2! 3!

n≥0 k≥0

LECTURE 3

Matroids and geometric lattices

3.1. Matroids

A matroid is an abstraction of a set of vectors in a vector space (for us, the normals

to the hyperplanes in an arrangement). Many basic facts about arrangements

(especially linear arrangements) and their intersection posets are best understood

from the more general viewpoint of matroid theory. There are many equivalent

ways to de¬ne matroids. We will de¬ne them in terms of independent sets, which

are an abstraction of linearly independent sets. For any set S we write

2S = {T : T ⊆ S}.

De¬nition 3.8. A (¬nite) matroid is a pair M = (S, I), where S is a ¬nite set and

I is a collection of subsets of S, satisfying the following axioms:

(1) I is a nonempty (abstract) simplicial complex, i.e., I = …, and if J ∈ I and

I ‚ J, then I ∈ I.

(2) For all T ⊆ S, the maximal elements of I © 2T have the same cardinality.

In the language of simplicial complexes, every induced subcomplex of I is

pure.

The elements of I are called independent sets. All matroids considered here will

be assumed to be ¬nite. By standard abuse of notation, if M = (S, I) then we write

x ∈ M to mean x ∈ S. The archetypal example of a matroid is a ¬nite subset S of

a vector space, where independence means linear independence. A closely related

matroid consists of a ¬nite subset S of an a¬ne space, where independence now

means a¬ne independence.

It should be clear what is meant for two matroids M = (S, I) and M = (S , I )

to be isomorphic, viz., there exists a bijection f : S ’ S such that {x1 , . . . , xj } ∈ I

if and only if {f (x1 ), . . . , f (xj )} ∈ I . Let M be a matroid and S a set of points in

Rn , regarded as a matroid with independence meaning a¬ne independence. If M

and S are isomorphic matroids, then S is called an a¬ne diagram of M . (Not all

matroids have a¬ne diagrams.)

Example 3.7. (a) Regard the con¬guration in Figure 1 as a set of ¬ve points in the

two-dimensional a¬ne space R2 . These ¬ve points thus de¬ne the a¬ne diagram

of a matroid M . The lines indicate that the points 1,2,3 and 3,4,5 lie on straight

31

32 R. STANLEY, HYPERPLANE ARRANGEMENTS

1 5

2 4

3

Figure 1. A ¬ve-point matroid in the a¬ne space R2

lines. Hence the sets {1, 2, 3} and {3, 4, 5} are a¬nely dependent in R2 and therefore

dependent (i.e., not independent) in M . The independent sets of M consist of all

subsets of [5] with at most two elements, together with all three-element subsets of

[5] except 123 and 345 (where 123 is short for {1, 2, 3}, etc.).

(b) Write I = S1 , . . . , Sk for the simplicial complex I generated by S1 , . . . , Sk ,

i.e.,

= {T : T ⊆ Si for some i}

S 1 , . . . , Sk

= 2 S1 ∪ · · · ∪ 2 Sk .

Then I = 13, 14, 23, 24 is the set of independent sets of a matroid M on [4]. This

matroid is realized by a multiset of vectors in a vector space or a¬ne space, e.g., by

the points 1,1,2,2 in the a¬ne space R. The a¬ne diagam of this matroid is given

by

1,2 3,4

(c) Let I = 12, 23, 34, 45, 15 . Then I is not the set of independent sets of a

matroid. For instance, the maximal elements of I © 2{1,2,4} are 12 and 4, which do

not have the same cardinality.

(d) The a¬ne diagram below shows a seven point matroid.

1 2

3

LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 33

If we further require the points labelled 1,2,3 to lie on a line (i.e., remove 123

from I), we still have a matroid M , but not one that can be realized by real vectors.

In fact, M is isomorphic to the set of nonzero vectors in the vector space F3 , where

2

F2 denotes the two-element ¬eld.

010

110 011

111