A SIMPLE BIJECTION FOR THE REGIONS OF THE SHI ARRANGEMENT OF HYPERPLANES

CHRISTOS A. ATHANASIADIS AND SVANTE LINUSSON

Abstract. The Shi arrangement S_{n} is the arrangement of affine hyperplanes in ℝ^{n} of the form x_{i}−x_{j} = 0 or 1, for 1 ≤ i < j ≤ n. It dissects ℝ^{n} into (n+1)^{n−1} regions, as was first proved by Shi. We give a simple bijective proof of this result. Our bijection generalizes easily to any subarrangement of S_{n} containing the hyperplanes x_{i} − x_{j} = 0 and to the extended Shi arrangements.

1. Introduction

A hyperplane arrangement A is a finite set of affine hyperplanes in ℝ^{n}. The regions of A are the connected components of the space obtained from ℝ^{n} by removing the hyperplanes of A. A classical example is provided by the braid arrangement A_{n}. It consists of the hyperplanes in ℝ^{n} of the form x_{i} = x_{j} for 1 ≤ i < j ≤ n, i.e. the reflecting hyperplanes of the Coxeter group of type A_{n−1}. Its regions correspond to permutations of the set [n] := {1, 2, …, n}.

A deformation of A_{n} [12] is an arrangement each of whose hyperplanes is parallel to one of the hyperplanes of A_{n}. We will be concerned with a deformation of A_{n} which has remarkable combinatorial properties. It is the Shi arrangement, denoted by S_{n}, and consists of the hyperplanes

x_{i} − x_{j} = 0 for 1 ≤ i < j ≤ n and

x_{i} − x_{j} = 1 for 1 ≤ i < j ≤ n (1)

in ℝ^{n}. Figure 1 shows S_{3} intersected with the plane x_{1} + x_{2} + x_{3} = 0. Shi was the first to consider S_{n} in his investigation of the affine Weyl group of type A_{n−1} [10]. He used techniques from group theory to prove the following result.

Theorem 1.1. (Shi [10, Cor. 7.3.10]) The number of regions of S_{n} is (n + 1)^{n−1}.

The Shi arrangement was further studied enumeratively by Headley [6, 7], Stanley [12, 13] and the first author [1, 2] and from the point of view of freeness in [3]. A simple proof of Theorem 1.1 was given in [1, §3] [2, §6.2] as an application of the “finite field method” of [1, 2]. It uses Zaslavsky’s theory of counting regions [15]. Another

Both authors were supported by the Mathematical Sciences Research Institute, Berkeley, California. The second author was also supported by the Swedish Science Council. Research at MSRI is supported in part by NSF grant DMS-9022140.

Figure 1. The Shi arrangement for n = 3.

simple proof of Theorem 1.1, using directly deletion and restriction, is implicit in [3, Thm. 3.1]. See the first remark in the last section.

Our objective here is to give a simple bijective proof. The only bijection already known is due to Pak and Stanley [12, §5]. They established a correspondence between the regions of S_{n} and the parking functions on [n], which are well known to be counted by (n+1)^{n−1}. Although this correspondence is easy to define, a lot of effort is needed, as well as Shi’s result itself, to prove that it is indeed a bijection (see the proof of [13, Thm. 2.1]). Our bijection can also be stated in terms of parking functions but is different from that of Pak and Stanley. It generalizes easily to any arrangement between A_{n} and S_{n} as follows. Let G be a simple graph on the vertex set [n]. We denote by S_{n,G} the arrangement

\begin{matrix}x_{i} − x_{j} = 0 for 1 ≤ i < j ≤ n, \\ x_{i} − x_{j} = 1 for 1 ≤ i < j ≤ n, ij ∈ G \end{matrix} (2)

in ℝ^{n}, first considered in [1, §3] [2, §6.2] and later in [3]. It specializes to A_{n} when G is empty and to S_{n} when G is the complete graph. Let ℤ_{n+1} denote the abelian group of integers modulo n + 1 and let H be the cyclic subgroup of ℤ_{n+1}^{n} generated by (1, 1, …, 1). One can think of ℤ_{n+1}^{n} as the set of all placements of n distinct balls into n + 1 identical boxes arranged cyclically.

Theorem 1.2. The regions of S_{n,G} are in bijection with the cosets

(a_{1}, a_{2}, …, a_{n}) + H ∈ ℤ_{n+1}^{n} /H (3)

which satisfy the following condition: given i, if j is the smallest integer such that i < j and a_{i} = a_{j}, then ij ∈ G.

Stanley [13] has generalized the correspondence of [12, §5] to a bijection between the regions of the extended Shi arrangement

x_{i} − x_{j} = −k + 1, −k + 2, …, k for 1 ≤ i < j ≤ n (4) and k-parking functions on [n], which are counted by (kn + 1)^{n−1}. Our bijection also generalizes easily in this direction.

This paper is organized as follows: Section 2 contains our new proof of Theorem 1.1. In Section 3 we prove the more general Theorem 1.2 and derive some special cases, previously obtained with non-bijective methods. We also generalize our bijection to the extended Shi arrangements. In Section 4 we give explicitly the proof of Theorem 1.1 which follows from the methods of [3] and close with some open problems.

2. The bijection

We first describe our bijection in terms of parking functions. A parking function on [n] is a map f : [n] ⟶ [n] such that for all 1 ≤ j ≤ n, the cardinality of the set f^{−1}([j]) is at least j. We also use the notation f = (a_{1}, a_{2}, …, a_{n}), where a_{i} = f(i) for 1 ≤ i ≤ n. Parking functions were first studied by Konheim and Weiss [8]. For the reason for the terminology “parking function” see [5, §2.6] [12, §5]. An extensive literature is given in [13].

In order to describe the bijection we index the regions of S_{n} as follows. First, given a region R, we consider only the x_{i} − x_{j} = 0 hyperplanes and let w = w_{1}w_{2} ⋯ w_{n} be the unique permutation of [n] such that x_{w_{1}} > x_{w_{2}} > ⋯ > x_{w_{n}} holds on R. Second, we draw an arc (i, j) in w from i to j if i < j and x_{i} − x_{j} > 1 holds on R. Third, we remove any arcs “containing” another arc. In other words, if there is an arc (j, k) then we remove any arcs (i, l), (i, k) or (j, l) if x_{i} > x_{j} > x_{k} > x_{l}, x_{i} > x_{j} or x_{k} > x_{l} holds on R respectively. Clearly, these arcs are forced by the arc (j, k) and hence redundant. The diagram of R is the resulting permutation of [n] with arcs going rightwards from smaller to larger integers, with no arc containing another.

Example. The region of S_{9} indexed by the diagram of Figure 2 is defined by the inequalities x_{2} > x_{4} > x_{6} > ⋯ > x_{7} > x_{3} and x_{2} − x_{4} < 1, x_{2} − x_{6} > 1, x_{4} − x_{6} < 1, x_{2} − x_{8} > 1 etc.

Figure 2. The diagram of a region of S_{9}

Note that for each diagram ρ, the arcs naturally determine a partition π = π_{ρ} of [n] into chains of increasing integers. In the example above, this partition is π = 269/457/8/13. We say that the position of m in ρ is j if m = w_{j}, i.e. if m is the jth integer from the left which appears in ρ.

Definition 2.1. Let σ_{n} be the map from the regions of S_{n} to parking functions on [n] which sends the region with diagram ρ to the function

f(i) = the position in ρ of the leftmost element in the chain containing i.

This is clearly a parking function, so σ_{n} is well defined. The region in our example is mapped by σ_{9} to the parking function (6, 1, 6, 2, 2, 1, 2, 4, 1).

Theorem 2.2 (Main Theorem). The map σ_{n} is a bijection between the regions of S_{n} and parking functions on [n].

Proof. We describe the inverse of σ_{n} explicitly. Given a parking function f, we get the partition π simply by placing i and j in the same block if f(i) = f(j). The chains are obtained by listing the elements of each block in increasing order, from left to right. It remains to determine the permutation. To do so, we place the chains relative to each other one at a time, in increasing order of their values under f. Assume that we have already placed the chains with values less than j and are to place the chain with value j. Since f is a parking function, there are at least j − 1 elements already placed. We insert the leftmost element of the chain in position j, counting from the left. There is a unique way to place the other elements of the chain to the right without forming any pair of arcs with one containing the other. This braiding defines a diagram ρ and hence a region R of S_{n}. We leave it to the reader to check that this map is indeed the inverse of σ_{n}.

Figure 3 illustrates the procedure to get back the region of S_{9} from the parking function for our example.

Figure 3. Constructing the region σ_{9}^{−1}(f)

Figure 4 shows the 16 parking functions of length 3 associated to the regions of S_{3}, according to σ_{3}.

The fact that there are (n + 1)^{n−1} parking functions on [n] follows from the observation, due to Pollack [4, p. 13] and repeated by Haiman [5, p. 28, 33] and Stanley [14, §2], that every coset in ℤ_{n+1}^{n} /H contains exactly one parking function. The following corollary proves Theorem 1.1.

Corollary 2.3. The map σ_{n} induces a bijection between the regions of S_{n} and elements of ℤ_{n+1}^{n} /H.

Figure 4. The bijection σ_{3}.

3. Generalizations

In this section we generalize Theorem 2.2 to the arrangements between A_{n} and S_{n} and derive some special cases, previously obtained by other methods. Also, in a different direction, we give a generalization to the extended Shi arrangements.

Arrangements between A_{n} and S_{n}. Recall the definition of S_{n,G} given in (2). A region R of S_{n,G} can be represented as a permutation w of [n] together with a set of arcs, as in the case of S_{n}. We now draw an arc (i, j) in w from i to j if i < j, ij ∈ G and x_{i} − x_{j} > 1 holds on R. We remove all redundant arcs, as before, to get the diagram of R. We define the map σ_{n,G} from the regions of S_{n,G} to parking functions as in Definition 2.1.

Theorem 3.1. The map σ_{n,G} is a bijection between the regions of S_{n,G} and the parking functions f = (a_{1}, a_{2}, …, a_{n}) which satisfy the following condition: given i, if j is the smallest integer such that i < j and a_{i} = a_{j}, then ij ∈ G.

Proof. Let R be a region of S_{n,G} with diagram ρ. For a chain i_{1} < i_{2} < ⋯ < i_{r} in ρ we have i_{k−1}i_{k} ∈ G for all 1 < k ≤ r by construction. Hence the associated parking function f = (a_{1}, a_{2}, …, a_{n}), for which a_{i_{1}} = a_{i_{2}} = ⋯ = a_{i_{r}}, has the property stated in the theorem. The inverse of σ_{n,G} is as in the special case of Theorem 2.2.

Theorem 1.2 follows immediately if we interpret parking functions as elements of ℤ_{n+1}^{n} /H, as in Section 2. As an application of Theorem 1.2 we obtain bijective proofs for two simple results from [1, 2]. The next theorem follows also from [3, Cor. 3.6].

Theorem 3.2. ([1, Thm. 3.4] [2, Thm. 6.2.2]) Suppose that the graph G has the following property: if 1 ≤ i < j < k ≤ n and ij ∈ G then ik ∈ G. Then the number of regions of S_{n,G} is the product

∏_{1<j≤n}(n − d_{j} + 1), (5)

where d_{j} = # {i < j | ij is not in G} for 1 < j ≤ n.

Proof. Under the given assumption on G, the cosets (3) of Theorem 1.2 are exactly the ones that satisfy the following condition: if i < j and a_{i} = a_{j} then ij ∈ G. It suffices to show that the number of such cosets is the product (5). Indeed, fix a value for a_{1} to break the cyclic symmetry and suppose we have chosen values a_{2}, …, a_{j−1} satisfying the condition. We want to choose a_{j} ∈ ℤ_{n+1} so that a_{j} ≠ a_{i} whenever i < j and ij not in G. These values a_{i} are all distinct, since for two such i_{1} < i_{2} < j, i_{1}i_{2} is not in G by the assumption on G and hence a_{i_{1}} ≠ a_{i_{2}} by the choice of a_{i_{2}}. It follows that there are d_{j} forbidden values for a_{j} and hence n − d_{j} + 1 allowable ones.

Theorem 3.3. ([1, Thm. 5.6] [2, Cor. 7.1.6]) Let G be the path {12, 23, …, (n−1)n}. The number of regions of S_{n,G} is the sum

∑_{k=1}^{n} \frac{n!}{k!} \binom{n − 1}{k − 1}.

Proof. Now a coset (3) satisfies the condition of Theorem 1.2 if and only if the entries which take any fixed value of ℤ_{n+1} form a string a_{i} = a_{i+1} = ⋯ = a_{j}. There are \binom{n−1}{n−k} = \binom{n−1}{k−1} ways to form n − k + 1 such strings and \frac{n!}{k!} ways to assign distinct values to them, modulo cyclic symmetry.

The extended Shi arrangements. Following [13], we denote by S_{n}^{k} the extended Shi arrangement (4). Stanley [13] has defined a k-parking function on [n] to be a sequence of positive integers f = (a_{1}, a_{2}, …, a_{n}) such that the unique increasing rearrangement b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} of the terms of f satisfies b_{i} ≤ 1 + k(i − 1) for all i. Thus a 1parking function is an ordinary parking function. He generalized the correspondence of [12, §5] to a bijection between the regions of S_{n}^{k} and k-parking functions on [n]. He also noted that, in agreement to the k = 1 case, k-parking functions on [n] are in bijection with the cosets of the cyclic subgroup of ℤ_{kn+1}^{n} generated by (1, 1, …, 1), where ℤ_{kn+1} is the abelian group of integers modulo kn + 1. Hence there are exactly (kn + 1)^{n−1} k-parking functions on [n].

We now generalize the bijection σ_{n} to treat the arrangements S_{n}^{k}. We associate a diagram to a region R of S_{n}^{k} as follows. First we consider only the hyperplanes x_{i}−x_{j} = l for −k+1 ≤ l ≤ k−1 and let y = y_{1} y_{2} ⋯ y_{kn} be the unique permutation of the variables x_{i}+m, where 1 ≤ i ≤ n and 0 ≤ m ≤ k−1, such that y_{1} > y_{2} > ⋯ > y_{kn} holds on R. We draw arcs in y going rightwards from x_{i} +m to x_{i} +m−1 for all i and m > 0. Second, we draw an arc from x_{i} to x_{j} +k −1 if i < j and x_{i} −x_{j} > k holds on R. Finally, we remove all arcs containing another arc and replace each variable x_{i}+m by i. The arcs determine naturally a partition of the multiset M_{n}^{k} = {1^{k}, 2^{k}, …, n^{k}} into chains of weakly increasing integers such that the elements of M_{n}^{k} equal to i appear all in the same chain.

Example. The diagram of Figure 5 represents the region of S_{4}^{2} defined by the inequalities x_{2} + 1 > x_{1} + 1 > x_{2} > x_{1} > x_{4} + 1 > x_{3} + 1 > x_{4} > x_{3}, x_{2} − x_{4} > 2 and x_{1} − x_{3} < 2. The corresponding partition of M_{4}^{2} = {1, 1, 2, 2, 3, 3, 4, 4} into chains is 2244/11/33.

Figure 5. The diagram of a region of S_{4}^{2}

Definition 3.4. We define the map σ_{n}^{k} by sending the region R of S_{n}^{k} with diagram ρ to the function f = (a_{1}, a_{2}, …, a_{n}) with

a_{i} = the position in ρ of the leftmost element of the chain containing all i’s.

As before, it is easy to check that f is a k-parking function. For the region of Figure 5 we have f = (2, 1, 6, 1).

Theorem 3.5. The map σ_{n}^{k} is a bijection between the regions of S_{n}^{k} and k-parking functions on [n].

Proof. We describe the inverse map of σ_{n}^{k}, as in the proof of Theorem 2.2. Let f = (a_{1}, a_{2}, …, a_{n}) be a k-parking function and b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} be the unique increasing rearrangement of its terms. For each value j of f, consider a chain C_{j} of positive integers, listed from left to right in increasing order. The chain C_{j} contains k copies of r if a_{r} = j and none otherwise. Place the chains one at a time, in order of increasing value j. If j = b_{i} > b_{i−1}, then there are k(i − 1) ≥ j − 1 elements listed before placing C_{j}, since f is a k-parking function. Insert the leftmost element of C_{j} in position j, counting from the left, and the other elements to the right so that no pair of arcs with one containing the other is formed. This defines the desired diagram, and hence region of S_{n}^{k}.

Figure 6 illustrates the bijection σ_{3}^{2}.

4. Remarks and open problems

1. The two other simple proofs of Theorem 1.1, mentioned in the introduction, come from computing the characteristic polynomial [9, §2.3] χ(S_{n}, q) of S_{n}. Assuming

Figure 6. The bijection σ_{3}^{2}

Shi’s result, Headley [6, 7] was the first to show that χ(S_{n}, q) = q(q − n)^{n−1}. This formula is immediate [1, Thm. 3.3] [2, Thm. 6.2.1] once one uses the finite field method to interpret combinatorially the values of χ(S_{n}, q) at large primes q. Zaslavsky’s theorem [15] expresses the number of regions r(A) of a hyperplane arrangement A in ℝ^{n} as (−1)^{n}χ(A, −1) and yields Theorem 1.1.

The computation of χ(S_{n}, q) by deletion and restriction in [3, Thm. 3.1] can be carried out on the level of the number of regions. It results in a naive inductive proof of Theorem 1.1, suitably generalized, which we describe explicitly next. Let A be a hyperplane arrangement and H ∈ A a distinguished hyperplane. The crucial and well known fact that we use below is that

r(A) = r(A′) + r(A′′), (6) where A′ = A − {H} is the corresponding deleted arrangement and A′′ = {H′ ∩ H | H′ ∈ A′} is the restricted arrangement to H. Note that A′′ is an arrangement in the affine space H.

Theorem 4.1. For any integers m ≥ 0 and 2 ≤ k ≤ n + 1, the arrangement x_{1} − x_{j} = 0, 1, …, m for 2 ≤ j < k,

x_{1} − x_{j} = 0, 1, …, m + 1 for k ≤ j ≤ n,
x_{i} − x_{j} = 0, 1 for 2 ≤ i < j ≤ n

(7)

has (n + m)^{k−2}(n + m + 1)^{n−k+1} regions. In particular, for m = 0 and k = 2, S_{n} has (n + 1)^{n−1} regions.

Proof. We proceed by double induction on n and n−k, the result being clear for n = 2. The case m = 0 and k = n + 1 follows easily from the result for S_{n−1}. Indeed, each of the n^{n−2} regions of S_{n−1} in the space spanned by x_{2}, …, x_{n} determines a linear order of these variables and there are n ways to form a region of (7) by inserting x_{1} in this order. We can now assume 2 ≤ k ≤ n, since the arrangement (7) having parameters m ≥ 1 and k = n+1 coincides with (7) having parameters m−1 and k = 2. Consider the hyperplane H of (7) with equation x_{1} − x_{k} = m + 1. The corresponding deleted arrangement has the same form as (7), with k replaced by k + 1, once one replaces x_{k} by x_{1} − m − 1. The restricted arrangement to H has again the same form, with n replaced by n − 1 and m replaced by m + 1. The result follows by the induction hypothesis on these two arrangements and (6).

2. Let k be any integer satisfying 1 ≤ k ≤ n. The number of faces of S_{n} of dimension k was shown [1, Thm. 6.5] [2, Cor. 8.2.1] to have the surprisingly simple combinatorial interpretation

f_{k}(S_{n}) = \binom{n}{k} # \{f : [n − 1] → [n + 1] | [n − k] ⊆ Imf\},

where Imf is the image of the map f. This formula reduces to Theorem 1.1 for k = n. The general case lacks a bijective proof and shows that the combinatorics of S_{n} is still not well understood. A similar interpretation was obtained for the extended Shi arrangements [2, Thm. 8.2.2].

3. Shi [11] has generalized Theorem 1.1 to the other irreducible crystallographic root systems. It would be interesting to find similar simple bijective proofs at least for the infinite families of type B, C and D.

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] D. Foata and J. Riordan, Mappings of acyclic and parking functions, Aequationes Math. 10 (1974), 10–22.

[5] M. D. Haiman, Conjectures on the quotient ring by diagonal invariants, J. Alg. Combin. 3 (1994), 17–76.

[6] P. Headley, On reduced words in affine Weyl groups, in Proc. “Formal Power Series and Algebraic Combinatorics (FPSAC) 1994” (L. J. Billera, C. Greene, R. Simion, R. Stanley, eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc. 24 (1996), pp. 225–232.

[7] P. Headley, Reduced expressions in infinite Coxeter groups, Ph.D. thesis, University of Michigan, 1994.

[8] A. G. Konheim and B. Weiss, An occupancy discipline and applications, SIAM J. Applied Math. 14 (1966), 1266–1274.

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

[10] J.-Y. Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lecture Notes in Mathematics, no. 1179, Springer-Verlag, Berlin/Heidelberg/New York, 1986.

[11] J.-Y. Shi, Sign types corresponding to an affine Weyl group, J. London Math. Soc. 35 (1987), 56–74.

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

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

[14] R. Stanley, Parking functions and noncrossing partitions, Preprint, August 1996.

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

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

E-mail address: athana@msri.org

Svante Linusson, Department of Mathematics, Stockholm University, S-106 91 Stockholm, SWEDEN

E-mail address: linusson@matematik.su.se