a c

b d

e

f

c d e

a b

Figure 5. An example of an interval order

The left-hand side of (43) is given by

t’n t(t ’ n)(t ’ n ’ 1) · · · (t ’ 2n + 1)

t[xt ]xt’n (1 + x)t’n = t = .

n n!

It follows that

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

for all t ∈ Z. It then follows easily (e.g., using the fact that a polynomial in one

variable over a ¬eld of characteristic 0 is determined by its values on Z) that this

equation holds when t is an indeterminate.

Note. It is not di¬cult to give an alternative proof of Theorem 5.18 based on

the ¬nite ¬eld method (Exercise 12).

5.5. Interval orders

The subject of interval orders has a long history (see [10][23]), but only recently

[20] was their connection with arrangements noticed. Let P = {I1 , . . . , In } be a

¬nite set of closed intervals Ii = [ai , bi ], where ai , bi ∈ R and ai < bi . Partially

order P by de¬ning Ii < Ij if bi < aj , i.e., Ii lies entirely to the left of Ij on the real

number line. A poset isomorphic to P is called an interval order. Figure 5 gives

an example of six intervals and the corresponding interval order. It is understood

that the real line lies below and parallel to the line segments labelled a, . . . , f , and

that the actual intervals are the projections of these line segments to R. If all the

intervals Ii have length one, then P is called a semiorder or unit interval order.

We will be considering both labelled and unlabelled interval orders. A labelled

interval order is the same as an interval order on a set S, often taken to be [n].

If an interval order P corresponds to intervals I1 , . . . , In , then there is a natural

72 R. STANLEY, HYPERPLANE ARRANGEMENTS

1 6 3 3 6

Figure 6. The number of labelings of semiorders with three elements

labeling of P , viz., label the element corresponding to Ii by i. Thus the intervals

I1 = [0, 1] and I2 = [2, 3] correspond to the labelled interval order P1 de¬ned by

1 < 2, while the intervals I1 = [2, 3] and I2 = [0, 1] correspond to P2 de¬ned by

2 < 1. Note that P1 and P2 are di¬erent labelled interval orders but are isomorphic

as posets. As another example, consider the intervals I1 = [0, 2] and I2 = [1, 3].

The corresponding labelled interval order P consists of the disjoint points 1 and 2.

If we now let I1 = [1, 3] and I2 = [0, 2], then we obtain the same labelled interval

order (or labelled poset) P , although the intervals themselves have been exchanged.

An unlabelled interval order may be regarded as an isomorphism class of interval

orders; two intervals orders P1 and P2 represent the same unlabelled interval order if

and only if they are isomorphic. Of course our discussion of labelled and unlabelled

interval orders applies equally well to semiorders.

Figure 6 shows the ¬ve nonisomorphic (or unlabelled) interval orders (which

for three vertices coincides with semiorders) with three vertices, and below them

the number of distinct labelings. (In general, the number of labelings of an n-

element poset P is n!/#Aut(P ), where Aut(P ) denotes the automorphism group

of P .) It follows that there are 19 labelled interval orders or labelled semiorders on

a 3-element set.

The following proposition collects some basic results on interval orders. We sim-

ply state them without proof. Only part (a) is needed in what follows (Lemma 5.6).

We use the notation i to denote an i-element chain and P +Q to denote the disjoint

union of the posets P and Q.

(a) A ¬nite poset is an interval order if and only if it has

Proposition 5.15.

no induced subposet isomorphic to 2 + 2.

(b) A ¬nite poset is a semiorder if and only if it has no induced subposet

isomorphic to 2 + 2 or 3 + 1.

(c) A ¬nite poset P is a semiorder if and only if its elements can be ordered as

I1 , . . . , In so that the incidence matrix of P (i.e., the matrix M = (mij ),

where mij = 1 if Ii < Ij and mij = 0 otherwise) has the form shown

below. Moreover, all such semiorders are nonisomorphic.

LECTURE 5. FINITE FIELDS 73

000 001 011 001 011

000 000 000 001 001

000 000 000 000 000

Figure 7. The semiorders with three elements

1 n

1

1

0

n

In (c) above, the southwest boundary of the positions of the 1™s in M form a

lattice path which by suitable indexing goes from (0, 0) to (n, n) with steps (0, 1)

and (1, 0), never rising above y = x. Since the number of such lattice paths is

the Catalan number Cn , it follows that the number of nonisomorphic n-element

semiorders is Cn . Later (Proposition 5.17) we will give a proof based on properties

of a certain arrangement. Figure 7 illustrates Proposition 5.15(c) when n = 3. It

shows the matrices M , the corresponding set of unit intervals, and the associated

semiorder.

Let 1 , . . . , n > 0 and set · = ( 1 , . . . , n ). Let P· denote the set of all interval

orders P on [n] such that there exist a set I1 , . . . , In of intervals corresponding to

P

P (with Ii corresponding to i ∈ P ) such that (Ii ) = i . In other words, i < j if

and only if Ii lies entirely to the left of Ij . For instance, it follows from Figure 6

that #P(1,1,1) = 19.

We now come to the connection with arrangements. Given · = ( 1 , . . . , n ) as

above, de¬ne the arrangement I· in Rn by letting its hyperplanes be given by

xi ’ x j = i, i = j.

(Note the condition i = j, not i < j.) Thus I· has rank n ’ 1 and n(n ’ 1)

hyperplanes (since i > 0). Figure 8 shows the arrangement I(1,1,1) in the space

ker(x1 + x2 + x3 ).

Proposition 5.16. Let · ∈ Rn . Then r(I· ) = #P· .

+

74 R. STANLEY, HYPERPLANE ARRANGEMENTS

Figure 8. The arrangement I(1,1,1) in the space ker(x1 + x2 + x3 )

Proof. Let (x1 , . . . , xn ) belong to some region R of I· . De¬ne the interval Ii =

[xi ’ i , xi ]. The region R is determined by whether xi ’ xj < i or xi ’ xj > i .

Equivalently, Ii > Ij or Ii > Ij in the ordering on intervals that de¬nes interval

orders. Hence the number of possible interval orders corresponding to intervals

I1 , . . . , In with (Ii ) = i is just r(I· ).

Consider the case 1 = · · · = n = 1, so we are looking at the semiorder

arrangement xi ’ xj = 1 for i = j. We abbreviate (1, 1, . . . , 1) as 1n and denote

this arrangement by I1n . By the proof of Proposition 5.16 the regions of I1n are in

a natural bijection with semiorders on [n].

Now note that Cn = I1n ∪ Bn , where Cn denotes the Catalan arrangement.

Fix a region R of Bn , say x1 < x2 < · · · < xn . Then the number of regions of

I1n that intersect R is the number of semiorders on [n] that correspond to (unit)

intervals I1 , . . . , In with right endpoints x1 < x2 < · · · < xn . Another set I1 , . . . , In

of unit intervals Ii = [xi ’ 1, xi ] with x1 < x2 < · · · < xn de¬nes a di¬erent

region from that de¬ned by I1 , . . . , In if and only if the corresponding semiorders