xi ± x j 1¤i<j¤n

= 0, 1,

1 ¤ i ¤ n,

2xi = 0, 1,

called the Shi arrangement of type B. Find the characteristic polynomial and

number of regions of SB . Is there a “nice” bijective proof of the formula for the

n

number of regions?

84 R. STANLEY, HYPERPLANE ARRANGEMENTS

(15) [5“] Let 1 ¤ k ¤ n. Find the number of regions (or more generally the charac-

teristic polynomial) of the arrangement (in Rn )

1, 1 ¤ i ¤ k

xi ’ x j =

2, k + 1 ¤ i ¤ n,

for all i = j. Thus we are counting interval orders on [n] where the elements

1, 2, . . . , k correspond to intervals of length one, while k + 1, . . . , n correspond

to intervals of length two. Is it possible to count such interval orders up to

isomorphism (i.e., the unlabelled case)? What if the length 2 is replaced instead

by a generic length a?

(16) [2+] A double semiorder on [n] consists of two binary relations < and on [n]

that arise from a set x1 , . . . , xn of real numbers as follows:

x i < xj ’ 1

i<j if

xi < xj ’ 2.

i j if

If we associate the interval Ii = [xi ’ 2, xi ] with the point xi , then we are

specifying whether Ii lies to the left of the midpoint of Ij , entirely to the left of

Ij , or neither. It should be clear what is meant for two double semiorders to be

isomorphic.

(a) [2] Draw interval diagrams of the 12 nonisomorphic double semiorders on

{1, 2, 3}.

(b) [2] Let ρ2 (n) denote the number of double semiorders on [n]. Find an

(2) (2)

arrangement In satisfying r(In ) = ρ2 (n).

(c) [2+] Show that the number of nonisomorphic double semiorders on [n] is

given by 2n+1 3n .

1

n

(d) [2“] Let F (x) = n≥0 2n+1 3n xn . Show that

1

n

xn

= F (1 ’ e’x ).

ρ2 (n)

n!

n≥0

(e) [2] Generalize to “k-semiorders,” where ordinary semiorders (or unit interval

orders) correspond to k = 1 and double semiorders to k = 2.

(17) [1+] Show that intervals of lengths 1, 1.0001, 1.001, 1.01, 1.1 cannot form an in-

terval order isomorphic to 4 + 1, but that such an interval order can be formed

if the lengths are 1, 10, 100, 1000, 10000.

(18) [5“] What more can be said about interval orders with generic interval lengths?

For instance, consider the two cases: (a) interval lengths very near each other

(e.g., 1, 1.001, 1.01, 1.1), and (b) interval lengths superincreasing (e.g., 1, 10, 100,

1000). Are there ¬nitely many obstructions to being such an interval order? Can

the number of unlabelled interval orders of each type be determined? (Perhaps

the numbers are the same, but this seems unlikely.)

(19) (a) [3] Let Ln denote the Linial arrangement, say in Rn . Show that

n

t n

(t ’ k)n’1 .

χLn (t) = n

2 k

k=1

(b) [1+] Deduce from (a) that

(’1)n χLn (’t + n)

χLn (t)

= .

’t + n

t

LECTURE 5. FINITE FIELDS 85

1 3 2 4 2 4 1 3

1 4 2 3 3 4 1 2

2 3 1 4

1 2

4

2 3

3

1

4

Figure 10. The seven alternating trees on the vertex set [4]

(20) (a) [3“] An alternating tree on the vertex set [n] is a tree on [n] such that

every vertex is either less than all its neighbors or greater than all its neigh-

bors. Figure 10 shows the seven alternating trees on [4]. Deduce from

Exercise 19(a) that r(Ln ) is equal to the number of alternating trees on

[n + 1].

(b) [5] Find a bijective proof of (a), i.e., give an explicit bijection between the

regions of Ln and the alternating trees on [n + 1].

(21) [3“] Let

χLn (t) = an tn ’ an’1 tn’1 + · · · + (’1)n’1 a1 t.

Deduce from Exercise 19(a) that ai is the number of alternating trees on the

vertex set 0, 1, . . . , n such that vertex 0 has degree (number of adjacent vertices)

i.

(22) (a) [2+] Let P (t) ∈ C[t] have the property that every (complex) zero of P (t)

has real part a. Let z ∈ C satisfy |z| = 1. Show that every zero of the

polynomial P (t ’ 1) + zP (t) has real part a + 1 . 2

(b) [2+] Deduce from (a) and Exercise 19(a) that every zero of the polynomial

χLn (t)/t has real part n/2. This result is known as the “Riemann hypothesis

for the Linial arrangement.”

(23) (a) [2“] Compute limn’∞ b(Sn )/r(Sn ), where Sn denotes the Shi arrangement.

(b) [3] Do the same for the Linial arrangement Ln .

(24) [2+] Let Ln denote the Linial arrangement in Rn . Fix an integer r = 0, ±1, and

let Mn (r) be the arrangement in Rn de¬ned by xi = rxj , 1 ¤ i < j ¤ n, together

with the coordinate hyperplanes xi = 0. Find a relationship between χLn (t) and

χMn (r) (t) without explicitly computing these characteristic polynomials.

(25) (a) [3“] A threshold graph on [n] may be de¬ned recursively as follows: (i) the

empty graph … is a threshold graph, (ii) if G is a threshold graph, then so is

the disjoint union of G and a single vertex, and (iii) if G is a threshold graph,

then so is the graph obtained by adding a new vertex v and connecting it

to every vertex of G. Let Tn denote the threshold arrangement. Show that

r(Tn ) is the number of threshold graphs on [n].

86 R. STANLEY, HYPERPLANE ARRANGEMENTS

(b) [2+] Deduce from (a) that

xn ex (1 ’ x)

r(Tn ) = .

2 ’ ex

n!

n≥0

(c) [1+] Deduce from Exercise 10 that

xn

= (1 + x)(2ex ’ 1)(t’1)/2 .

χTn (t)

n!

n≥0

(26) [5“] Let

χTn (t) = tn ’ an’1 tn’1 + · · · + (’1)n a0 .

For instance,

= t3 ’ 3t2 + 3t ’ 1

χT3 (t)

= t4 ’ 6t3 + 15t2 ’ 17t + 7

χT4 (t)

= t5 ’ 10t4 + 45t3 ’ 105t2 + 120t ’ 51.