PILES OF CUBES, MONOTONE PATH POLYTOPES AND HYPERPLANE ARRANGEMENTS

CHRISTOS A. ATHANASIADIS

Abstract. Monotone path polytopes arise as a special case of the construction of fiber polytopes, introduced by Billera and Sturmfels. A simple example is provided by the permutahedron, which is a monotone path polytope of the standard unit cube. The permutahedron is the zonotope polar to the braid arrangement. We show how the zonotopes polar to the cones of certain deformations of the braid arrangement can be realized as monotone path polytopes. The construction is an extension of that of the permutahedron and yields interesting connections between enumerative combinatorics of hyperplane arrangements and geometry of monotone path polytopes.

1. Introduction

Fiber polytopes were introduced by Billera and Sturmfels [5] and were further studied in [6]. The fiber polytope Σ(P, Q) is a polytope naturally associated to any projection of polytopes π : P ⟶ Q. It is defined as

(1) Σ(P, Q) = \{\frac{1}{vol(Q)} ∫_{Q} γ(x) dx | γ is a section of π\} .

A concise introduction to the theory of fiber polytopes can be found in Chapter 9 of Ziegler’s book [14], on which we rely for general background on polytopes.

We are only interested in the special case in which Q is one dimensional, i.e. a line segment. The polytope Σ(P, Q) is then called the monotone path polytope of P and π [5, §5] [14, §9.2] and is denoted by Π(P, π). Its dimension is one less than that of P. The sections of π are the paths in P which are monotone, that is strictly increasing with respect to the function π, and maximal, i.e. they project to Q. The vertices of Π(P, π) correspond to certain maximal monotone edge paths on P, called π-coherent.

A nice example of a monotone path polytope is the permutahedron Π_{d−1} ⊆ ℝ^{d}. The permutahedron Π_{d−1} is a classical geometric object. It is the convex hull of all vectors in ℝ^{d} obtained by permuting the coordinates of the vector (1, 2, …, d). It was constructed as a monotone path polytope of the standard unit cube C_{d} = [0, 1]^{d} by Billera and Sturmfels [5, Example 5.4] (see also [6, Thm. 4.3]). A detailed description of the construction can be found in [14, Example 9.8]. The projection used is π : C_{d} ⟶ [0, d] with

Supported by a postdoctoral fellowship from the Mathematical Sciences Research Institute, Berkeley, California. Research at MSRI is supported in part by NSF grant DMS-9022140.

π(x) = x_{1} + x_{2} + ⋯ + x_{d}. (2)

The monotone edge paths from the origin to the vertex (1, 1, …, 1) are all π-coherent. They correspond naturally to permutations of a d-element set and give rise to the vertices of Π_{d−1}. This is illustrated in Figure 1 for d = 3.

Figure 1. The projection π and the permutahedron

An important property of Π_{d−1} is that it is a zonotope. The associated hyperplane arrangement [14, §7.3] is the braid arrangement A_{d}. It consists of the hyperplanes in ℝ^{d} of the form x_{i} = x_{j} for 1 ≤ i < j ≤ d, i.e. the reflecting hyperplanes of the Coxeter group of type A_{d−1}. Our motivation comes from recent work on deformations of A_{d}, initiated by Stanley [11]. A deformation of A_{d} is an affine arrangement which has each of its hyperplanes parallel to some hyperplane x_{i} = x_{j} of A_{d}. We will be interested in the deformations of the form

x_{i} − x_{j} = −λ_{i} + 1, …, −1, 0, 1, …, λ_{j} − 1 for 1 ≤ i < j ≤ d, (3)

where λ = (λ_{1}, λ_{2}, …, λ_{d}) is a composition of a positive integer n. We denote the arrangement (3) by A_{d}(λ). For λ_{1} = ⋯ = λ_{d} = a + 1 it specializes to the extended Catalan arrangement (see for example [11, §2]) and is denoted by A_{d}^{[0,a]}. This reduces to the braid arrangement A_{d} for a = 0 and is simply called a Catalan arrangement for a = 1. Figure 2 shows the Catalan arrangement for d = 3, intersected with the hyperplane x_{1} + x_{2} + x_{3} = 0.

The combinatorics of deformations of A_{d} is very rich and has a growing literature [11, 12, 3, 10]. The zonotopes associated to the corresponding homogenized linear

Figure 2. The Catalan arrangement for d = 3

arrangements, or cones, haven’t been studied much as polytopes. They are generalizations of the permutahedron that carry the same interesting combinatorial structure as the arrangements. Our objective is to construct the zonotopes associated to the cones of the arrangements A_{d}(λ), with their Minkowski summands suitably rescaled, as monotone path polytopes.

The construction generalizes that of the permutahedron. In particular, the cube C_{d} is replaced by Ziegler’s lifted pile of cubes P̃_{d+1}(λ) [14, §5.1], which we define formally in the next section. The projection π is given by the formula (2). The corresponding monotone path polytope Π_{d}(λ) is a zonotope, as described above, with its upper part truncated. The maximal monotone edge paths in the lower faces of P̃_{d+1}(λ) are in bijection with the lattice paths in ℝ^{d} from the origin to the point λ, having unit coordinate steps. In general, most of these paths are not coherent. The coherent ones correspond to the lower vertices of the zonotope and hence to the regions of A_{d}(λ). This will enable us to enumerate them (see Corollary 4.3) by an easy application of the “finite field method” of [1, 2]. It follows that their number is small compared to the total number of lower monotone edge paths.

The paper is organized as follows: In Section 2 we give the necessary definitions and state our main results about Π_{d}(λ). Section 3 contains a proof of the main theorem. In Section 4 we draw all enumerative consequences of the main theorem by analyzing the combinatorics of A_{d}(λ). We also characterize the coherent paths in the lower faces of P̃_{d+1}(λ) directly from the definition. We close with some remarks in Section 5.

2. Basic definitions and results

We begin with some notation and terminology. We denote by e_{1}, e_{2}, …, e_{d} the unit coordinate vectors in ℝ^{d}. We write [a, b] for the line segment joining two points a, b ∈ ℝ^{d}. The canonical projection ℝ^{d+1} ⟶ ℝ^{d} is the map which simply forgets the last coordinate. Lastly, we refer to the union of the lower faces [14, §5.1], or upper faces, of a polytope P as its lower part, or upper part respectively.

We first give the definition of the polytope P̃_{d+1}(λ), as promised in the introduction. Let λ = (λ_{1}, λ_{2}, …, λ_{d}) be a composition of a positive integer n. In other words, the λ_{i} are positive integers which sum to n. The pile of cubes P_{d}(λ), corresponding to λ, is the polytopal complex formed by all unit cubes with integer vertices in the d-box

B(λ) = {(x_{1}, …, x_{d}) ∈ ℝ^{d} | 0 ≤ x_{i} ≤ λ_{i} for 1 ≤ i ≤ d} .

In particular, the vertex set of P_{d}(λ) is

vert (P_{d}(λ)) = B(λ) ∩ ℤ^{d}.

Let f : ℝ^{d} ⟶ ℝ be of the form

f(x) = f_{1}(x_{1}) + ⋯ + f_{d}(x_{d}) (4)

where the f_{i}’s are strictly convex functions of one variable. For the purpose of our results we will use the canonical choice

f(x) = x_{1}^{2} + x_{2}^{2} + ⋯ + x_{d}^{2}.

We take this as the definition of f from now and on. The lifted pile of cubes corresponding to λ is the polytope in ℝ^{d+1}

P̃_{d+1}(λ) = conv {(x, f(x)) | x ∈ vert (P_{d}(λ))} .

The pile of cubes P_{d}(λ) and its lift P̃_{d+1}(λ) are discussed in [14, Example 5.4]. For suitable λ they provide examples of polytopal complexes, respectively polytopes, which are not extendably shellable [14, Ch. 8]. Figure 3 shows P_{2}(4, 3) and its lift P̃_{3}(4, 3).

The lower faces of P̃_{d+1}(λ) form a polytopal complex combinatorially equivalent to P_{d}(λ). Because of the form (4), these faces are parallelepipeds, as Figure 3 suggests. By construction, they map to the corresponding faces of P_{d}(λ) under the canonical projection ℝ^{d+1} ⟶ ℝ^{d}. The unique upper facet, defined by the hyperplane

λ_{1}x_{1} + λ_{2}x_{2} + ⋯ + λ_{d}x_{d} = x_{d+1}, (5)

is a parallelepiped which projects to B(λ).

Let Π_{d}(λ) be the monotone path polytope of the projection

π : P̃_{d+1}(λ) ⟶ [0, n]

given by the formula (2). Thus π(x) is the sum of the first d coordinates of x ∈ ℝ^{d+1}. We have dim Π_{d}(λ) = dim P̃_{d+1}(λ) − 1 = d, the number of parts of λ except if λ_{i} = 1 for all i. In this case P̃_{d+1}(λ) is affinely isomorphic to the d-cube C_{d}, so Π_{d}(λ) is affinely isomorphic to the permutahedron Π_{d−1} and dim Π_{d}(λ) = d − 1.

Figure 3. P_{2}(4, 3) and P̃_{3}(4, 3)

A truncation of a polytope P in ℝ^{r} is its intersection with a closed halfspace a · x ≤ 0, where a ∈ ℝ^{r}. We call such a truncation an upper truncation if it includes the lower part of P but does not intersect the upper part in the region a · x < 0. In particular, an upper truncation has a unique upper facet. It rarely happens that a polytope P has an upper truncation. However, if P is a zonotope with a sufficiently large Minkowski summand in the direction of the last coordinate, as in the situation of the next theorem, then clearly, upper truncations exist.

Theorem 2.1. Let Z_{d}(λ) be the zonotope

[0, s e_{d+1}] + ∑_{1≤i<j≤d} ∑_{k=0}^{λ_{i}−1} ∑_{l=0}^{λ_{j}−1} [0, e_{j} − e_{i} + (2l − 2k) e_{d+1}] ,

where s is a sufficiently large positive number. The polytope Π_{d}(λ) is an upper truncation of a translate of \frac{1}{n}Z_{d}(λ), cut by the hyperplane (5).

Note that the hyperplane arrangement associated to Z_{d}(λ) is projectively equivalent to the cone of A_{d}(λ), denoted cA_{d}(λ). This is the linear arrangement in ℝ^{d+1} obtained by homogenizing each hyperplane x_{i} − x_{j} = s of A_{d}(λ) to x_{i} − x_{j} = sx_{d+1} and adding the hyperplane x_{d+1} = 0. Hence Z_{d}(λ) is combinatorially equivalent to the zonotope Z[cA_{d}(λ)], associated to this cone, which we call the polar zonotope. The faces of Z[cA_{d}(λ)] are in inclusion-reversing bijection with the faces of cA_{d}(λ) [14, Cor. 7.17]. Its lower faces define a zonotopal complex Z[A_{d}(λ)] which we call the polar zonotopal complex, or simply the polar complex. The faces of Z[A_{d}(λ)] are in inclusion-reversing bijection with those of A_{d}(λ). Figure 4 shows the complex polar to the Catalan arrangement of Figure 2, projected canonically on ℝ^{2}.

Figure 4. The polar complex

We now focus on the the lower part, which is the interesting part of Π_{d}(λ). Theorem 2.1 implies the following corollary.

Corollary 2.2. The complex of all lower faces of Π_{d}(λ) is combinatorially equivalent to the polar complex Z[A_{d}(λ)] of the arrangement A_{d}(λ). In particular, the lower vertices of Π_{d}(λ) are in bijection with the regions of A_{d}(λ).

Hence, for λ = (2, 2, 2), Π_{d}(λ) looks combinatorially like the complex of Figure 4, from a point far below on the x_{3} axis.

It follows from Corollary 2.2 that the π-coherent monotone edge paths in the lower part of P̃_{d+1}(λ) are in bijection with the regions of A_{d}(λ). To characterize them, we introduce some more terminology. We call the maximal monotone edge paths (with respect to π) in P_{d}(λ) simply monotone λ-paths. They are the lattice paths in ℝ^{d} from the origin to the point λ having n unit coordinate steps. They correspond naturally to permutations of the multiset M_{λ}, which contains i with multiplicity λ_{i} for 1 ≤ i ≤ d. We call these permutations λ-permutations and denote by p^{w} the monotone λ-path which corresponds to w. For example, if λ = (2, 2, 2) and w = 121323 then the path p^{w} has successive steps e_{1}, e_{2}, e_{1}, e_{3}, e_{2}, e_{3}. The number of λ-permutations is the multinomial coefficient \binom{n}{λ_{1},... ,λ_{d}}.

The maximal monotone edge paths in the lower part of P̃_{d+1}(λ) are in bijection with the monotone λ-paths, via the canonical projection ℝ^{d+1} ⟶ ℝ^{d}. We refer to these paths in P̃_{d+1}(λ) as lifted monotone λ-paths and use the notation γ^{w}.

A λ-permutation w = w_{1}w_{2} ⋯ w_{n} is nesting if there exist indices 1 ≤ i < j < k < l ≤ n such that w_{i} = w_{l}, w_{j} = w_{k} and w_{m} ≠ w_{i} for all m with j ≤ m ≤ k. Otherwise w is non-nesting. Equivalently, w is non-nesting if the following linear system in the variables y_{1}, y_{2}, …, y_{n} is feasible:

(i) y_{1} < y_{2} < ⋯ < y_{n}, (ii) y_{k} = y_{j} + 1 if 1 ≤ j < k ≤ n, w_{k} = w_{j} and w_{m} ≠ w_{j} for j < m < k. For example, 12121 is non-nesting but 12211 is not.

Theorem 2.3. The lifted monotone λ-path γ^{w} is π-coherent if and only if w is nonnesting. The number of such paths, or equivalently the number of lower vertices of Π_{d}(λ), or regions of A_{d}(λ) is \frac{n!}{(n−d+1)!}. In particular, this quantity depends only on n and d.

It follows that the fraction of monotone λ-paths with π-coherent lifts is

\frac{λ_{1}!λ_{2}! ⋯ λ_{d}!}{(n − d + 1)!}.

This result gives concrete examples of projections for which the fraction of coherent monotone edge paths is explicitly shown to be small. For instance, in the case λ_{1} = ⋯ = λ_{d} = 2 this quantity becomes 2^{d}/(d + 1)!. The only other fiber polytope situation we are aware of, in which it has been shown that the number of coherent subdivisions is asymptotically negligible compared to the number of all subdivisions, appears in [7] in the context of triangulations of cyclic d-polytopes with d+4 vertices.

3. Proof of the main theorem

We now prove Theorem 2.1.

Proof of Theorem 2.1 : We use directly the defining formula (1). Recall that the vertices of Π_{d}(λ) correspond to certain maximal monotone edge paths γ in P̃_{d+1}(λ). Since π(x) depends only on the first d coordinates of x, we only need to consider such paths either in the lower or upper part of P̃_{d+1}(λ) and take the convex hull of the right hand side of (1). Let

I_{γ} := \frac{1}{vol(Q)} ∫_{[0,n]} γ(x) dx = \frac{1}{n} ∑_{k=1}^{n} \frac{γ(k − 1) + γ(k)}{2}.

We first consider the lower part of P̃_{d+1}(λ), so the relevant paths are the lifted monotone λ-paths γ^{w}. Instead of calculating I_{γ^{w}} explicitly, we note that any λpermutation w can be obtained from w_{0} = 1 ⋯ 1 ⋯ d ⋯ d by successively swapping adjacent entries ij with i < j. Let w = w_{1}w_{2} ⋯ w_{n}, where w_{k} = i < j = w_{k+1} and let w′ be obtained from w by swapping w_{k} and w_{k+1}. If v := γ^{w}(k −1) = γ^{w′}(k −1) = (m_{1}, m_{2}, …, m_{d}), then

I_{γ^{w′}} − I_{γ^{w}} = \frac{1}{n} (γ^{w′}(k) − γ^{w}(k)) =

\frac{1}{n} (v + e_{j} + f(v + e_{j}) e_{d+1} − v − e_{i} − f(v + e_{i}) e_{d+1}) =
\frac{1}{n} (e_{j} − e_{i} + (2m_{j} − 2m_{i}) e_{d+1}) .

It follows easily that the points I_{γ^{w}} lie on \frac{1}{n}Z_{d}(λ) + I_{γ^{w_{0}}} and include all its lower vertices.

Finally suppose that γ lies in the upper facet of P̃_{d+1}(λ), which is defined by the hyperplane (5). This upper facet projects to the d-box B(λ) under the canonical projection ℝ^{d+1} ⟶ ℝ^{d}. Each of the monotone edge paths γ projects to a monotone λ-path with corresponding λ-permutation of the form w = σ_{1} ⋯ σ_{1} ⋯ σ_{d} ⋯ σ_{d}, where σ_{1} ⋯ σ_{d} is a permutation of {1, 2, …, d}. Hence I_{γ} = I_{γ^{w}} + te_{d+1} for some t ≥ 0. Since γ lies on (5), so does I_{γ}. It follows that the upper part of Π_{d}(λ) also consists of a single facet, defined by (5). It projects to the same zonotope on ℝ^{d}, which is combinatorially equivalent to the permutahedron Π_{d−1}, as the lower part. This completes the proof.

4. The coherent paths and enumeration

In this section we characterize and enumerate the π-coherent lifted monotone λpaths and thus prove Theorem 2.3. We proceed directly from the definition of a coherent path and extend our argument to get another proof of Corollary 2.2. For the enumeration we use the finite field method of [1, 2].

We first recall what it means for a monotone edge path to be coherent. Let P be a polytope in ℝ^{r}, π : ℝ^{r} ⟶ ℝ an affine function, Q = π(P) ⊆ ℝ and p a maximal monotone edge path in P. The path p is said to be π-coherent if there exists a generic linear functional c ∈ (ℝ^{r})^{∗} such that π^{c} : ℝ^{r} ⟶ ℝ^{2} with

π^{c}(x) = (π(x), c(x))

maps p to the path of lower edges of the polygon Q^{c} := π^{c}(P). More generally [14, Definition 9.2], a set of faces F of P is said to form a π-coherent subdivision of Q if, for some c ∈ (ℝ^{r})^{∗}, F is the set F^{c} of faces (π^{c})^{−1} (G) of P, where G runs through the lower faces of Q^{c}. Note that F^{c} induces the subdivision {π(F) : F ∈ F^{c}} of Q. This is also the subdivision obtained by projecting canonically the lower edges of Q^{c} on Q. The set F^{c} consists of faces of P, rather than Q.

For the rest of this section let r = d + 1, P = P̃_{d+1}(λ), Q = [0, n] and π as in Section 2.

Proposition 4.1. The lifted monotone λ-path γ^{w} is π-coherent if and only if w is non-nesting. The non-nesting λ-permutations are in bijection with the regions of the arrangement A_{d}(λ).

Proof. Let c ∈ (ℝ^{d+1})^{∗} be generic and given by

c(x) = a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{d+1}x_{d+1}. (6)

We need to describe the π-coherent path defined by c, directly in terms of c. Since we want this path to lie in the lower part of P̃_{d+1}(λ), we can assume that a_{d+1} is positive, say a_{d+1} = 1/2 by rescaling.

Let w = w_{1}w_{2} ⋯ w_{n} be a λ-permutation and p^{w}, γ^{w} as in Section 2, with p^{w} = (v_{0}, v_{1}, …, v_{n}) and γ^{w} = (ṽ_{0}, ṽ_{1}, …, ṽ_{n}). Thus v_{k} = v_{k−1} + e_{i} if w_{k} = i and ṽ_{k} = (v_{k}, f(v_{k})) for all k. We denote by Δ^{c}(w) the sequence of length n whose kth term records the difference

c(ṽ_{k}) − c(ṽ_{k−1})

of c at the kth edge of γ^{w}. Let v_{k−1} = (m_{1}, …, m_{d}) and w_{k} = i. Then

c(ṽ_{k}) − c(ṽ_{k−1}) = a_{i} + a_{d+1} (f(v_{k−1} + e_{i}) − f(v_{k−1})) =
a_{i} + (1/2) (2m_{i} + 1) = a′_{i} + m_{i},

where a′_{i} = a_{i} + 1/2 for 1 ≤ i ≤ d and the possible values of m_{i} are the integers satisfying 0 ≤ m_{i} ≤ λ_{i} − 1. It follows that Δ^{c}(w) is the permutation of the numbers

a′_{i} + m, 0 ≤ m ≤ λ_{i} − 1, 1 ≤ i ≤ d (7)

which places a′_{i}, a′_{i} + 1, …, a′_{i} + λ_{i} − 1, in this order, in the λ_{i} positions occupied by i in w. The numbers (7) are distinct because c is assumed to be generic.

Let w^{c} be the λ-permutation which corresponds to the π-coherent path defined by c. If π^{c} maps γ^{w} to the lower edge path of the polygon Q^{c}, then Δ^{c}(w) is strictly increasing, by the convexity of this path. It follows that w^{c} is the unique λ-permutation w for which the permutation Δ^{c}(w) of the numbers (7) is strictly increasing. Let c′ = (a′_{1}, a′_{2}, …, a′_{d}) ∈ ℝ^{d}. For a fixed λ-permutation w, if nonempty, the set of all c′ such that w^{c} = w forms exactly a region of A_{d}(λ). Indeed, deciding which of the two numbers a′_{i} + m and a′_{j} + l in (7) is smaller amounts to choosing a side of the hyperplane x_{i} − x_{j} = l − m of A_{d}(λ). Finally, w = w^{c} for some c if and only if the condition that Δ^{c}(w) is strictly increasing does not impose inequalities of the form

d_{j} < d_{i} < d_{i} + 1 < d_{j} + 1.

By definition, this means that w is non-nesting.

We now compute the number of regions of A_{d}(λ). We assume familiarity with the characteristic polynomial χ(A, q) of A [9, §2.3], a fundamental combinatorial invariant of A, and use Zaslavsky’s theorem [13] for the number of regions of A. The characteristic polynomial of A_{d}(λ) can be computed by an easy application of the finite field method of [1] [2, Part II]. This method reduces the computation to a simple counting problem in a vector space over a finite field. The argument in the following proposition is similar to the one given in [1, Thm. 5.1] for the special case of the extended Catalan arrangements.

Proposition 4.2. We have

χ(A_{d}(λ), q) = q ∏_{j=n−d+1}^{n−1}(q − j).

Proof. Let q be a large prime number and let 𝔽_{q} denote the finite field of integers mod q. Theorem 2.2 in [1] (also [2, Thm. 5.2.1]) implies that χ(A_{d}(λ), q) counts the number of d-tuples (x_{1}, x_{2}, …, x_{d}) ∈ 𝔽_{q}^{d} satisfying

x_{i} − x_{j} ≠ −λ_{i} + 1, …, −1, 0, 1, …, λ_{j} − 1 for 1 ≤ i < j ≤ d.

Equivalently, we want to choose the x_{i} so that the classes mod q

x_{i}, x_{i} + 1, …, x_{i} + λ_{i} − 1 for 1 ≤ i ≤ d (8)

are distinct. To count these d-tuples we first cyclically permute the d strings (8) in (d − 1)! ways. Then we distribute q − n indistinguishable boxes in the d spaces between successive strings in \binom{q−n+d−1}{d−1} ways. The q − n boxes distributed stand for the q − n classes in 𝔽_{q} not of the form (8). Finally we assign to x_{1} a specific value in 𝔽_{q} in q ways, say x_{1} = 0. The other classes of (8) x_{1} + 1, … and the boxes are naturally assigned the values 1, …, q −1 ∈ 𝔽_{q}, according to their cyclic arrangement. The product

q (d − 1)! \binom{q − n + d − 1}{d − 1}

is the expression for χ(A_{d}(λ), q) we have claimed.

Zaslavsky’s theorem [13] expresses the number of regions of an arrangement A in ℝ^{d} as (−1)^{d}χ(A, −1) and yields the following corollary.

Corollary 4.3. The number of regions of A_{d}(λ) is

\frac{n!}{(n − d + 1)!}.

In particular, this number depends only on n and d, the sum and number of parts of λ respectively.

Figure 5 shows the arrangement A_{d}(λ) for λ = (3, 2, 1), intersected with the hyperplane x_{1} + x_{2} + x_{3} = 0. Note that it has 30 regions, as many as the Catalan arrangement of Figure 4, which corresponds to λ = (2, 2, 2). Corollary 4.3 specializes to the formula given in [11, §2] for the number of regions of the extended Catalan arrangement A_{d}^{[0,a]}, since in this case n = (a + 1)d. Proposition 4.1 and Corollary 4.3 imply Theorem 2.3.

Figure 5. The arrangement A_{3}(3, 2, 1)

The reasoning in the proof of Proposition 4.1 can be extended to determine the face lattice of Π_{d}(λ). Below we give an alternative proof of Corollary 2.2, obtained in this way. By the general theory of fiber polytopes [5, Thm. 2.1] [14, Thm. 9.6], the face lattice of Π_{d}(λ) is isomorphic to the poset of π-coherent subdivisions of Q = [0, n], with a minimal element adjoined. In this poset we have F_{1} ≤ F_{2} if the union of the faces in F_{1} is contained in the union of the faces in F_{2}.

Alternative proof of Corollary 2.2 : To get the lower faces of Π_{d}(λ) we consider linear functionals c ∈ (ℝ^{d+1})^{∗} as in (6), with positive a_{d+1}, but not necessarily generic. Let P^{c} denote the set of monotone λ-paths whose lifts lie in F^{c}, so that P^{c} is a singleton if c is generic. Note that F^{c_{1}} ≤ F^{c_{2}} in the poset of π-coherent subdivisions if and only if P^{c_{1}} ⊆ P^{c_{2}}. Using the notation in the proof of Proposition 4.1, we have p^{w} ∈ P^{c} if and only if Δ^{c}(w) is weakly increasing. It follows that P^{c_{1}} ⊆ P^{c_{2}} if and only if the faces F_{1}, F_{2} of A_{d} which contain c′_{1} and c′_{2} respectively satisfy F_{1} ≥ F_{2} in the face poset of A_{d}.

A precise description of the π-coherent lower subdivisions is given in Remark 2 of the next section. The computations of general face numbers of the extended Catalan arrangements [2, Ch. 8] can be translated in terms of the lower part of Π_{d}(λ) via Corollary 2.2. The following corollary, for example, follows from [2, Cor. 8.3.2], which computes the face numbers of the Catalan arrangement.

Corollary 4.4. For λ = (2, 2, …, 2) and 1 ≤ k ≤ d, the number of lower faces of Π_{d}(λ) of dimension d − k is

∑_{r=k}^{d} (r − 1)! S(d, r) \binom{r}{k}\binom{r + k}{k − 1},

where S(d, k) stands for a Stirling number of the second kind.

5. Remarks

1. A direct bijective proof of Corollary 4.3 is possible and is outlined next.

Alternative proof of Corollary 4.3 : Recall that a region of A_{d}(λ) is defined by a linear ordering τ_{1} < τ_{2} < ⋯ < τ_{n} of

x_{i} + m, 0 ≤ m ≤ λ_{i} − 1, 1 ≤ i ≤ d

which respects the orderings x_{i} < x_{i} + 1 < ⋯ < x_{i} + λ_{i} − 1 for 1 ≤ i ≤ d and is such that the λ-permutation obtained by replacing each x_{i}+m with i is non-nesting. Given such an ordering τ with corresponding permutation w = w_{1}w_{2} ⋯ w_{n}, let j_{1}, j_{2}, …, j_{d} be the positions in which x_{1}, x_{2}, …, x_{d} appear in τ respectively. In other words, j_{i} is the smallest j such that w_{j} = i. Consider the quotient of the abelian group ℤ_{n+1}^{d} by the cyclic subgroup H generated by (1, 1, …, 1). The map

τ ⟶ J_{τ} = (j_{1}, j_{2}, …, j_{d}) + H

defines a bijection between the regions of A_{d}(λ) and cosets J = (j_{1}, j_{2}, …, j_{d}) + H of ℤ_{n+1}^{d}/H for which all j_{i} are mutually distinct. Clearly, the number of such cosets is n(n − 1) ⋯ (n − d + 2).

2. Let π : P ⟶ Q be as in the beginning of Section 4. The poset of π-coherent subdivisions of Q is an induced subposet of the poset ω(P, Q) of all π-induced subdivisions of Q [14, Definition 9.1] (see also [4, §3]). In the special case dim Q = 1 we are considering, this is the poset of cellular strings of P, induced by π [4, §1]. The π-induced subdivisions in the lower part P = P̃_{d+1}(λ) form an interesting poset, which we denote by Ω(λ). It is the set of all proper ordered partitions of the multiset M_{λ}, partially ordered by refinement. An ordered partition of M_{λ} is proper if none of its blocks contains repeated elements. The subdivision defined by ρ = (B_{1}, B_{2}, …, B_{k}) ∈ Ω(λ) has as maximal faces the lifts of the faces

∑_{i=1}^{j−1} e_{B_{i}} + ∑_{r∈B_{j}}[0, e_{r}], 1 ≤ j ≤ k

of P_{d}(λ), where e_{B} = ∑_{i∈B} e_{i}. Figure 6 shows the faces of P_{2}(4, 3) which correspond to the proper ordered partition (1, 12, 2, 12, 1) of M_{λ} = {1, 1, 1, 1, 2, 2, 2}, with λ = (4, 3). The minimal elements of Ω(λ) are the λ-permutations, which give rise to the lifted monotone λ-paths.

The argument in the proof of Corollary 2.2 in Section 4 yields the following description of the subposet of π-coherent lower subdivisions: Let ρ = (B_{1}, B_{2}, …, B_{k}) ∈ Ω(λ), as before. For each 1 ≤ i ≤ d replace the entries in the blocks of ρ equal to i, from left to right, with x_{i}, x_{i} + 1, …, x_{i} + λ_{i} − 1 respectively, to get ρ′ = (B′_{1}, B′_{2}, …, B′_{k}). The π-induced subdivision defined by ρ is coherent if and only if the following linear system in the variables x_{1}, x_{2}, …, x_{d} is feasible:

Figure 6. The subdivision defined by (1, 12, 2, 12, 1)

(i) u = v whenever u, v are in the same block B′_{j}, (ii) u < v whenever u ∈ B′_{j}, v ∈ B′_{l} and j < l.

In this case, the set of solutions forms exactly a face of A_{d}(λ). The subdivision of Figure 6 is not coherent because the system

x_{1} < x_{1} + 1 = x_{2} < x_{2} + 1 < x_{1} + 2 = x_{2} + 2 < x_{1} + 3

has no solution. The only coherent atom of Ω(4, 3) smaller than this subdivision is (1, 2, 1, 2, 1, 2, 1).

3. There is a notion of “flip” on the set of all maximal monotone edge paths p of P with respect to the affine function π. Two such paths are said to be related by a flip if they have a common cover in the poset ω(P, Q) of π-induced subdivisions of Q. We call the minimum number of flips required to make p coherent the incoherency of p. In the case of lifted monotone λ-paths γ^{w}, the operation of flipping swaps two distinct successive entries ij of w. Therefore the incoherency of γ^{w} is the minimum number of swappings needed to make w non-nesting. To get a feeling for this number, we compute the maximum incoherency that can occur for λ = (2, 2, …, 2).

Proposition 5.1. Let λ = (2, 2, …, 2). The maximum incoherency of a path γ^{w} is \binom{d}{2} and is attained by the λ-permutations of the form w_{σ} = σ_{1} σ_{2} ⋯ σ_{d} σ_{d} ⋯ σ_{2} σ_{1}, where σ = σ_{1} σ_{2} ⋯ σ_{d} is a permutation of {1, …, d}.

Proof. Every flip can reduce the number of “nestings” of w by at most one and w^{σ} has the maximum number \binom{d}{2} of nestings. On the other hand, any w = w_{1}w_{2} ⋯ w_{2d} can be turned into some w_{σ} by at most \binom{d}{2} flips in the following way: Suppose that w_{1}, …, w_{i} are mutually distinct but w_{i+1} = w_{k} for some 1 ≤ k ≤ i. Let j be the smallest index with j > i for which w_{j} ≠ w_{1}, …, w_{i}. Move w_{j} to the left until it occupies position i + 1. Continue in the same way until the first d entries of the permutation are all distinct, say σ_{1}, σ_{2}, …, σ_{d}. Now continue flipping in the second half of the permutation, in an obvious way, to get w_{σ} for σ = σ_{1} σ_{2} ⋯ σ_{d}. Any two distinct integers i, j are flipped at most once during the whole process, so the total number of flips is at most \binom{d}{2}, as desired.

4. The extended Catalan arrangements form one of the two families of deformations of A_{d} for which explicit formulas have been obtained for the number of faces of any given dimension [2, Ch. 8]. The other family consists of the extended Shi arrangements

x_{i} − x_{j} = −a + 1, −a + 2, …, a for 1 ≤ i < j ≤ d,

where a ≥ 1 is an integer. The number of faces in each dimension was shown to have a surprisingly simple combinatorial interpretation [2, Thm. 8.2.1]. We don’t know if a fiber polytope construction for the polar complexes exists in this case.

5. The cones of the extended Catalan arrangements A_{d}^{[0,a]} were shown to be inductively free [9, Ch. 4] by Edelman and Reiner (see the proof of Theorem 3.2 in [8]). Other classes of deformations of A_{d}, including the extended Shi arrangements, were shown to be inductively free in [3]. Proposition 4.2 suggests that the same is true for the arrangements A_{d}(λ).

Acknowledgement. I am grateful to Lou Billera and Bernd Sturmfels for helpful discussions.

References

[1] C. A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Advances in Math. 122 (1996), 193–233.

[2] C. A. Athanasiadis, Algebraic combinatorics of graph spectra, subspace arrangements and Tutte polynomials, Ph.D. thesis, MIT, 1996.

[3] C. A. Athanasiadis, On free deformations of the braid arrangement, Preprint 526/1996, TU-Berlin, July 1996, 17 pages.

[4] L. J. Billera, M. M. Kapranov and B. Sturmfels, Cellular strings on polytopes, Proc. Amer. Math. Soc. 122 (1994), 549–555.

[5] L. J. Billera and B. Sturmfels, Fiber polytopes, Annals of Math. 135 (1992), 527–549.

[6] L. J. Billera and B. Sturmfels, Iterated fiber polytopes, Mathematika 41 (1994), 348–363.

[7] J. A. de Loera, S. Hoşten, F. Santos and B. Sturmfels, The polytope of all triangulations of a point configuration, Doc. Math. 1 (1996), 103–119.

[8] P. H. Edelman and V. Reiner, Free arrangements and rhombic tilings, Discrete Comput. Geom. 15 (1996), 307–340.

[9] P. Orlik and H. Terao, Arrangements of Hyperplanes, Grundlehren 300, Springer-Verlag, New York, NY, 1992.

[10] A. Postnikov and R. Stanley, Deformations of Coxeter hyperplane arrangements, in preparation.

[11] R. Stanley, Hyperplane arrangements, interval orders and trees, Proc. Nat. Acad. Sci. 93 (1996), 2620–2625.

[12] R. Stanley, Hyperplane arrangements, parking functions and tree inversions, in Festschrift in Honor of Gian-Carlo Rota, Birkhäuser, Boston/Basel/Berlin, to appear.

[13] T. Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. vol. 1, no. 154, (1975).

[14] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics 152 Springer-Verlag, New York, 1995.

Christos A. Athanasiadis, Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720

  E-mail address: athana@msri.org