nomial.

Lemma 2.2. (Deletion-Restriction) Let (A, A , A ) be a triple of real arrange-

ments. Then

χA (t) = χA (t) ’ χA (t).

LECTURE 2. PROPERTIES OF THE INTERSECTION POSET 15

Figure 1. Two non-lattices

For the proof of this lemma, we will need some tools. (A more elementary proof

could be given, but the tools will be useful later.)

Let P be a poset. An upper bound of x, y ∈ P is an element z ∈ P satisfying

z ≥ x and z ≥ y. A least upper bound or join of x and y, denoted x ∨ y, is an upper

bound z such that z ¤ z for all upper bounds z . Clearly if x ∨ y exists, then it

is unique. Similarly de¬ne a lower bound of x and y, and a greatest lower bound

or meet, denoted x § y. A lattice is a poset L for which any two elements have a

meet and join. A meet-semilattice is a poset P for which any two elements have

a meet. Dually, a join-semilattice is a poset P for which any two elements have a

join. Figure 1 shows two non-lattices, with a pair of elements circled which don™t

have a join.

Lemma 2.3. A ¬nite meet-semilattice L with a unique maximal element ˆ is a1

lattice. Dually, a ¬nite join-semilattice L with a unique minimal element ˆ is a

0

lattice.

Proof. Let L be a ¬nite meet-semilattice. If x, y ∈ L then the set of upper bounds

of x, y is nonempty since ˆ is an upper bound. Hence

1

x∨y = z.

z≥x

z≥y

The statement for join-semilattices is by “duality,” i.e., interchanging ¤ with ≥,

and § with ∨.

The reader should check that Lemma 2.3 need not hold for in¬nite semilattices.

Proposition 2.3. Let A be an arrangement. Then L(A) is a meet-semilattice. In

particular, every interval [x, y] of L(A) is a lattice. Moreover, L(A) is a lattice if

and only if A is central.

Proof. If H∈A H = …, then adjoin … to L(A) as the unique maximal element,

obtaining the augmented intersection poset L (A). In L (A) it is clear that x ∨ y =

x©y. Hence L (A) is a join-semilattice. Since it has a ˆ it is a lattice by Lemma 2.3.

0,

16 R. STANLEY, HYPERPLANE ARRANGEMENTS

Since L(A) = L (A) or L(A) = L (A) ’ {ˆ it follows that L(A) is always a meet-

1},

semilattice, and is a lattice if A is central. If A isn™t central, then x∈L(A) x does

not exist, so L(A) is not a lattice.

We now come to a basic formula for the M¨bius function of a lattice.

o

Theorem 2.2. (the Cross-Cut Theorem) Let L be a ¬nite lattice. Let X be a subset

of L such that ˆ ∈ X, and such that if y ∈ L, y = ˆ then some x ∈ X satis¬es

0 0,

x ¤ y. Let Nk be the number of k-element subsets of X with join ˆ Then

1.

ˆˆ

µL (0, 1) = N0 ’ N1 + N2 ’ · · · .

We will prove Theorem 2.2 by an algebraic method. Such a sophisticated proof

is unnecessary, but the machinery we develop will be used later (Theorem 4.13).

Let L be a ¬nite lattice and K a ¬eld. The M¨bius algebra of L, denoted A(L), is

o

the semigroup algebra of L over K with respect to the operation ∨. (Sometimes

the operation is taken to be § instead of ∨, but for our purposes, ∨ is more con-

venient.) In other words, A(L) = KL (the vector space with basis L) as a vector

space. If x, y ∈ L then we de¬ne xy = x ∨ y. Multiplication is extended to all

of A(L) by bilinearity (or distributivity). Algebraists will recognize that A(L) is

a ¬nite-dimensional commutative algebra with a basis of idempotents, and hence

is isomorphic to K #L (as an algebra). We will show this by exhibiting an explicit

∼

=

isomorphism A(L) ’ K #L. For x ∈ L, de¬ne

µ(x, y)y ∈ A(L),

(8) σx =

y≥x

where µ denotes the M¨bius function of L. Thus by the M¨bius inversion formula,

o o

σy , for all x ∈ L.

(9) x=

y≥x

Equation (9) shows that the σx ™s span A(L). Since #{σx : x ∈ L} = #L =

dim A(L), it follows that the σx ™s form a basis for A(L).

Theorem 2.3. Let x, y ∈ L. Then σx σy = δxy σx , where δxy is the Kronecker

delta. In other words, the σx ™s are orthogonal idempotents. Hence

K · σx (algebra direct sum).

A(L) =

x∈L

Proof. De¬ne a K-algebra A (L) with basis {σx : x ∈ L} and multiplication

σx σy = δxy σx . For x ∈ L set x = s≥x σs . Then

« «

σs σt

xy =

s≥x t≥y

= σs

s≥x

s≥y

= σs

s≥x∨y

= (x ∨ y) .

Hence the linear transformation • : A(L) ’ A (L) de¬ned by •(x) = x is an

algebra isomorphism. Since •(σx ) = σx , it follows that σx σy = δxy σx .

LECTURE 2. PROPERTIES OF THE INTERSECTION POSET 17

Note. The algebra A(L) has a multiplicative identity, viz., 1 = ˆ = x∈L σx .

0

Proof of Theorem 2.2. Let char(K) = 0, e.g., K = Q. For any x ∈ L, we

have in A(L) that

ˆ’x = σy ’

0 σy = σy .

y≥x

y≥ˆ y≥x

0

Hence by the orthogonality of the σy ™s we have

(ˆ ’ x) =

0 σy ,

y

x∈X

where y ranges over all elements of L satisfying y ≥ x for all x ∈ X. By hypothesis,

the only such element is ˆ Hence

0.

(ˆ ’ x) = σˆ .

0 0

x∈X

If we now expand both sides as linear combinations of elements of L and equate

coe¬cients of ˆ the result follows.

1,

Note. In a ¬nite lattice L, an atom is an element covering ˆ Let T be the set

0.

of atoms of L. Then a set X ⊆ L ’ {ˆ satis¬es the hypotheses of Theorem 2.2 if

0}

and only if T ⊆ X. Thus the simplest choice of X is just X = T .

Example 2.5. Let L = Bn , the boolean algebra of all subsets of [n]. Let X = T =

{{i} : i ∈ [n]}. Then N0 = N1 = · · · = Nn’1 = 0, Nn = 1. Hence µ(ˆ ˆ = (’1)n ,

0, 1)

agreeing with Proposition 1.2.

We will use the Crosscut Theorem to obtain a formula for the characteristic

polynomial of an arrangement A. Extending slightly the de¬nition of a central

arrangement, call any subset B of A central if H∈B H = …. The following result

is due to Hassler Whitney for linear arrangements. Its easy extension to arbitrary

arrangements appears in [13, Lemma 2.3.8].

Theorem 2.4. (Whitney™s theorem) Let A be an arrangement in an n-dimensional