(2) [2] Draw a picture of the projectivization of the Coxeter arrangement A(B 3 ),

similar to Figure 1 of Lecture 1.

(3) (a) [2] An embroidered permutation of [n] consists of a permutation w of [n]

together with a collection E of ordered pairs (i, j) such that:

• 1 ¤ i < j ¤ n for all (i, j) ∈ E.

• If (i, j) and (h, k) are distinct elements of E, then it is false that

i ¤ h ¤ k ¤ j.

• If (i, j) ∈ E then w(i) < w(j).

For instance, the three embroidered permutations (w, E) of [2] are given

by (12, …), (12, {(1, 2)}), and (21, …). Give a bijective proof that the num-

ber r(Sn ) of regions of the Shi arrangement Sn is equal to the number of

embroidered permutations of [n].

(b) [2+] A parking function of length n is a sequence (a1 , . . . , an ) ∈ Pn whose

increasing rearrangement b1 ¤ b2 ¤ · · · ¤ bn satis¬es bi ¤ i. For instance,

the parking functions of length three are 11, 12, 21. Give a bijective proof

that the number of parking functions of length n is equal to the number of

embroidered permutations of [n].

(c) [3“] Give a combinatorial proof that the number of parking functions of

length n is equal to (n + 1)n’1 .

(4) [2+] Show that if Sn denotes the Shi arrangement, then the cone cSn is not

supersolvable for n ≥ 3.

(5) [2] Show that if f : P ’ R and h : N ’ R are related by equation (40) (with

h(0) = 1), then equation (39) holds.

(6) (a) [2] Compute the characteristic polynomial of the arrangement Bn in Rn

with de¬ning polynomial

Q(x) = (x1 ’ xn ’ 1) (xi ’ xj ).

1¤i<j¤n

In other words, Bn consists of the braid arrangement together with the

hyperplane x1 ’ xn = 1.

(b) [5“] Is cBn (the cone over Bn ) supersolvable?

(7) [2+] Let 1 ¤ k ¤ n. Find the characteristic polynomial of the arrangement Sn,k

in Rn de¬ned by

xi ’ xj = 0 for 1 ¤ i < j ¤ n

xi ’ xj = 1 for 1 ¤ i < j ¤ k.

(8) [2+] Let 1 ¤ k ¤ n. Find the characteristic polynomial of the arrangement Cn,k

in Rn de¬ned by

xi = 0 for 1 ¤ i ¤ n

xi ± xj = 0 for 1 ¤ i < j ¤ n .

xi + xj = 1 for 1 ¤ i < j ¤ k.

2k

In particular, show that r(Cn,k ) = 2n’k n! .

k

82 R. STANLEY, HYPERPLANE ARRANGEMENTS

(9) (a) [2+] Let An be the arrangement in Rn with hyperplanes xi = 0 for all i,

xi = xj for all i < j, and xi = 2xj for all i = j. Show that

χAn (t) = (t ’ 1)(t ’ n ’ 2)n’1 ,

where (x)m = x(x ’ 1) · · · (x ’ m + 1). In particular, r(An ) = 2(2n +

1)!/(n + 2)!. Can this be seen combinatorially? (This last question has not

been worked on.)

(b) [2+] Now let An be the arrangement in Rn with hyperplanes xi = xj for

all i < j and xi = 2xj for all i = j. Show that

χAn (t) = (t ’ 1)(t ’ n ’ 2)n’3 (t2 ’ (3n ’ 1)t + 3n(n ’ 1)).

In particular, r(An ) = 6n2 (2n ’ 1)!/(n + 2)!. Again, a combinatorial proof

can be asked for.

(c) [5“] Modify. For instance, what about the arrangement with hyperplanes

xi = 0 for all i, xi = xj for all i < j, and xi = 2xj for all i < j? Or xi = 0

for all i, xi = xj for all i < j, xi = 2xj for all i = j, and xi = 3xj for all

i = j?

(10) (a) [2+] For n ≥ 1 let An be an arrangement in Rn such that every H ∈ An

is parallel to a hyperplane of the form xi = cxj , where c ∈ R. Just as in

the de¬nition of an exponential sequence of arrangements, de¬ne for every

subset S of [n] the arrangement

AS = {H ∈ An : H is parallel to some xi = cxj , where i, j ∈ S}.

n

Suppose that for every such S we have LAS ∼ LAk , where k = #S. Let

=

n

xn

n

F (x) = (’1) r(An )

n!

n≥0

xn

rk(An )

G(x) = (’1) b(An ) .

n!

n≥0

Show that

xn G(x)(t+1)/2

(48) χAn (t) = .

F (x)(t’1)/2

n!

n≥0

(b) [2] Simplify equation (48) when each An is a central arrangement. Make

sure that your simpli¬cation is valid for the braid arrangement and the

coordinate hyperplane arrangement.

(11) [2+] Let R0 (Cn ) denote the set of regions of the Catalan arrangement Cn con-

ˆ

tained in the regions x1 > x2 > · · · > xn of Bn . Let R be the unique region

in R0 (Cn ) whose closure contains the origin. For R ∈ R0 (Cn ), let XR be the

ˆ

set of hyperplanes H ∈ Cn such that R and R lie on di¬erent sides of H. Let

Wn = {XR : R ∈ R0 (Cn )}, ordered by inclusion.

LECTURE 5. FINITE FIELDS 83

e

c d

c e

b

b d

a

a

W3

Let Pn be the poset of intervals [i, j], 1 ¤ i < j ¤ n, ordered by reverse

inclusion.

[1,2] [2,3] [3,4]

[1,2] [2,3]

[1,3] [2,4]

[1,3]

[1,4]

P3 P

4

Show that Wn ∼ J(Pn ), the lattice of order ideals of Pn . (An order ideal of a

=

poset P is a subset I ⊆ P such that if x ∈ I and y ¤ x, then y ∈ I. De¬ne J(P )

to be the set of order ideals of P , ordered by inclusion. See [18, Thm. 3.4.1].)

(12) [2] Use the ¬nite ¬eld method to prove that

χCn (t) = t(t ’ n ’ 1)(t ’ n ’ 2)(t ’ n ’ 3) · · · (t ’ 2n + 1),

where Cn denotes the Catalan arrangement.

(13) [2+] Let k ∈ P. Find the number of regions and characteristic polynomial of the

extended Catalan arrangement

Cn (k) : xi ’ xj = 0, ±1, ±2, . . . , ±k, for 1 ¤ i < j ¤ n.

Generalize Exercise 11 to the arrangements Cn (k).

(14) [3“] Let SB denote the arrangement