SIGN TYPES ASSOCIATED TO POSETS

Jian-yi Shi Department of Mathematics, East China Normal University, Shanghai, 200062, P.R.China and School of Mathematics and Statistics, The University of Sydney, Sydney, NSW 2006, Australia

Abstract. We start with a combinatorial definition of I-sign types which are a generalization of the sign types indexed by the root system of type A_{l} (I ⊂ ℕ finite). Then we study the set D_{p}^{I} of I-sign types associated to the partial orders on I. We establish a 1-1 correspondence between D_{p}^{[n]} and a certain set of convex simplexes in a euclidean space by which we get a geometric distinction of the sign types in D_{p}^{[n]} from the other [n]-sign types. We give a graph-theoretical criterion for an S_{n}-orbit O of D_{p}^{[n]} to contain a dast and show that O contains at most one dast. Finally, we show the admirability of a poset associated to a dast.

§0. Introduction. 0.1. Sign types indexed by the root system Φ of type A_{l} were first introduced in the middle of the eighties for the description of the Kazhdan-Lusztig cells in the affine Weyl group W_{a}(Ã_{l}) of type Ã_{l} (see [8, 10]). Subsequently they were extended to the case where the root system Φ is of an arbitrary type (see [9]). These sign types were defined originally as the connected components of the complement in a euclidean space spanned by Φ after removing a certain set of hyperplanes, which are now known as admissible sign types. The cardinalities of the admissible sign types and some of its subfamilies were obtained in all the cases (see [8, 9, 11]). Recently sign types indexed by the root system of type A_{l} have been studying

Typeset by AMS-TEX 2 JIAN-YI SHI

Supported by a grant from the Australian Research Council.

extensively as hyperplane arrangements by quite a number of people (see [2, 3, 5, 6, 12, 13]). 0.2. In the present paper, we make some further developments for the sign types indexed by the root system of type A_{l}. All the sign types mentioned in this paper are assumed in this case, but with slightly generalized forms. We start with a combinatorial definition of sign types. By this definition, the admissible sign types form only a special family, which belong to a larger and also important family of sign types associated to finite posets. We define the admissibility of a sign type also in a combinatorial way, although it is equivalent to the original definition by geometry. The new definition has the advantage that it is easier to be applied in the theoretic study. 0.3. The set D_{p}^{I} of sign types associated to finite posets of the underlying set I ⊂ ℕ is the main object studied in this paper, where ℕ is the set of natural numbers. Let [n] = {1, 2, ⋯, n} for n ∈ ℕ. We establish the connections of D_{p}^{[n]} with some other mathematical objects, such as digraphs, convex simplexes, partitions of a positive integer, and use them to get a number of properties of these sign types. We use the admissible sign types to describe a sign type in D_{p}^{[n]} and establish a 1-1 correspondence between the set D_{p}^{[n]} and a certain set of convex simplexes in a euclidean space, by which we distinguish the elements of D_{p}^{[n]} from D^{[n]} − D_{p}^{[n]} (set difference), where D^{[n]} is the set of all the [n]-sign types (see 4.5 and Theorem 4.7). 0.4. We define an action of the symmetric group S_{n} on D_{p}^{[n]}, which induces a bijection between the set of S_{n}-orbits in D_{p}^{[n]} and the set of isomorphism classes of posets of cardinality n. We consider the intersections of an S_{n}-orbit O of D_{p}^{[n]} with some special sign type sets, such as D_{a}^{[n]}, D_{da}^{[n]}, D_{d̂a}^{[n]}, the sets of admissible, dominant admissible, anti-dominant admissible [n]-sign types respectively. An S_{n}- orbit O of D_{p}^{[n]} can be represented by the isomorphic class of a digraph G = (V, E) (called a poset graph) with vertex set V and arrow set E. Then a sign type

SIGN TYPES ASSOCIATED TO POSETS 3

contained in O can be represented by a labeling τ : V ⟶ [n] of G, or equivalently by a labeled poset graph G(τ). Then that O contains an element of D_{a}^{[n]} (resp. D_{da}^{[n]}, resp. D_{d̂a}^{[n]}) is amount to the existence of an admissible (resp. dominant admissible, resp. anti-dominant admissible) labeling of G. We show that a poset graph G has at most one (up to congruence) dominant admissible labeling, exactly one if and only if G is nice (see 5.1.). This implies that an S_{n}-orbit of D_{p}^{[n]} contains at most one dominant admissible sign type (or dast for short), exactly one if and only if the corresponding poset graph is nice (see Theorem 5.2). Finally we show that the poset ([n], ⩽_{X}) associated to a dast X is admirable (see 6.2 and Theorem 6.7). This result has been applied to give a new characterization of Lusztig’s afunction on the cells of the affine Weyl group W_{a}(Ã_{l}) in terms of positive roots of certain parabolic subgroups and in terms of tilting modules (see [7]).

0.5. We can also characterize a poset graph to have an admissible or anti-dominant admissible labeling. But this will be more complicated than the case of having a dominant admissible labeling. We shall deal with this in a forthcoming paper.

0.6. The content of the paper is organized as below. We define sign types and introduce some general concepts related to sign types in section 1. Then in the subsequent sections, we pay a special attension to the set D_{p}^{I} of I-sign types associated to partial orders on I. We discuss the relations of D_{p}^{I} with some other sets of sign types in section 2. We introduce poset graphs and their labelings in section 3. The main results of the paper are included in sections 4-6. In section 4, we establish a 1-1 correspondence between D_{p}^{[n]} and a certain set of convex simplexes in a euclidean space by which we get a geometric distinction between the set D_{p}^{[n]} and its complement in D^{[n]}. In section 5, we give a graph-theoretical criterion for an S_{n}-orbit O of D_{p}^{[n]} to contain a dast and show that O contains at most one dast. Finally, we show the admirability of a poset associated to a dast in section 6.

4 JIAN-YI SHI

§1. Sign types. 1.1. Let I be a finite subset. By an I-sign type (or just a sign type), we mean a matrix X = (X_{ij})_{i,j∈I} over the symbol set Ξ = {+, ◯, −} subject to the requirement: for any i, j ∈ I

(1.1.1)  {X_{ij}, X_{ji}} ∈ {{+, −}, {◯,◯}}.

X is determined entirely by the “upper-unitriangular ”part X^{Δ} = (X_{ij})_{i<j} of the matrix. So we can identify X with X^{Δ}.

Let D^{I} be the set of all the I-sign types.

An I-sign type X is regular, if all the entries X_{ij}, i ≠ j are in the set {+, −}. When (I, ⩽) is a totally ordered set, we can define some more kinds of I-sign

types X = (X_{ij})_{i,j∈I} as below. X is dominant (resp. anti-dominant) if for any i < j in I, we have X_{ij} ∈ {+, ◯} (resp. X_{ij} ∈ {−, ◯}).

Let D_{r}^{I} (resp. D_{d}^{I}, resp. D_{d̂}^{I}) be the set of all the regular (resp. dominant, resp. anti-dominant) I-sign types.

The above definitions of sign types can be extended to the case where I is a poset. In particular, when I is a trivial poset (i.e. a set without any relation among elements), any I-sign type is dominant and anti-dominant. Of course, this case is not interesting to us. In the present paper, we always assume that I is a finite subset of ℕ. Thus I is totally ordered. We are particularly interested in the case where I = [n] for some n ∈ ℕ. The root system of type A_{n−1} can be expressed as Φ = {(i, j) | i ≠ j in [n]}. Thus an [n]-sign type X = (X_{ij})_{i,j∈[n]} is essentially a Φ-sign type (X_{ij})_{i≠j}, the latter can be obtained from X by removing all the entries X_{ii}, i ∈ [n], which are all ◯.

Symbolically, one may think of a sign type as a skew-symmetric matrix over the prime field of characteristic 3 or over the set {−1, 0, 1}.

SIGN TYPES ASSOCIATED TO POSETS 5

1.2. Example In the case where I = [3], we arrange the entries of the upperunitriangular part of an I-sign type X in the following way.

\begin{matrix}X_{13} \\ X_{12} X_{23} \end{matrix} .

Then there are 2^{3} different I-sign types in total, displayed as below.

(1) \begin{matrix}◯ \\ ◯ & ◯ \end{matrix} (2) − ◯^{◯} (3) ◯ −^{◯} (4) \begin{matrix}− \\ − ◯ \end{matrix} (5) \begin{matrix}− \\ ◯ − \end{matrix} (6) \begin{matrix}− \\ − − \end{matrix} (7) \begin{matrix}− \\ + − \end{matrix}
(8) \begin{matrix}− \\ − + \end{matrix} (9) \begin{matrix}+ \\ − + \end{matrix} (10) \begin{matrix}+ \\ + − \end{matrix} (11) {+ \atop + +} (12) \begin{matrix}+ \\ ◯ + \end{matrix} (13) \begin{matrix}+ \\ + ◯ \end{matrix} (14) +_{◯ ◯}
(15) + −^{◯} (16) − +^{◯} (17) ◯ +^{◯} (18) −_{◯ ◯} (19) + ◯^{◯} (20) − −^{◯} (21) \begin{matrix}+ \\ − ◯ \end{matrix}
(22) \begin{matrix}+ \\ ◯ − \end{matrix} (23) + +^{◯} (24) \begin{matrix}− \\ + ◯ \end{matrix} (25) \begin{matrix}− \\ ◯ + \end{matrix} (26) \begin{matrix}− \\ + + \end{matrix} (27) \begin{matrix}+ \\ − − \end{matrix}

1.3. An I-sign type X = (X_{ij}) is admissible, if for any i < j < k in I, we have

− ∈ {X_{ij}, X_{jk}} ⟹ X_{ik} ⩽ max{X_{ij}, X_{jk}}, (1.3.1) − ∉ {X_{ij}, X_{jk}} ⟹ X_{ik} ⩾ max{X_{ij}, X_{jk}}, (1.3.2) where we set a total ordering on the symbols: − < ◯ < +.

Let I_{c} be the set of all the triples (i, j, k) in I^{3} such that the sequence i, j, k is a cycle permutation of their natural (weak) increasing ordering. Then in the above definition, the condition “any i < j < k in I ”can be equivalently replaced by “any (i, j, k) ∈ I_{c} ”.

Let D_{a}^{I} be the set of all the admissible I-sign types. Let D_{da}^{I} = D_{a}^{I} ∩ D_{d}^{I}, D_{ra}^{I} = D_{a}^{I} ∩ D_{r}^{I} and D_{d̂a}^{I} = D_{a}^{I} ∩ D_{d̂}^{I} (see 1.1).

In Example 1.2, sign types (1), (11)-(14) are dominant admissible, (1)-(6) antidominant admissible, (6)-(11) regular admissible, and (1)-(16) admissible.

The cardinalities of the sets D_{ra}^{[n]}, D_{da}^{[n]}, D_{d̂a}^{[n]} and D_{a}^{[n]} are known for any n ∈ ℕ (see [8, 9, 11]).

The following result can be deduced directly from the definition.

6 JIAN-YI SHI

Lemma 1.4. Let X = (X_{ij})_{i<j} ∈ D_{a}^{I}, and let X^{+} (resp. X^{∘}) in D^{I} be obtained from X by replacing all the entries ◯ (resp. +) by + (resp. ◯) at the positions (i, j), i < j. Then we also have X^{+}, X^{∘} ∈ D_{a}^{I}. In particular, X ⟶ X^{+} is a bijective map from D_{d̂a}^{I} to D_{ra}^{I}. 1.5. The admissibility of an [n]-sign type can be interpreted geometrically for any n > 1.

Let E = {(a_{1}, ⋯, a_{n}) ∈ ℝ^{n} | ∑_{i=1}^{n} a_{i} = 0}. This is a euclidean space of dimension n − 1 with inner product (a_{1}, ⋯, a_{n}) · (b_{1}, ⋯, b_{n}) = ∑_{i=1}^{n} a_{i}b_{i}. For any i, j, ϵ ∈ ℤ with 1 ⩽ i < j ⩽ n, define a hyperplane

H_{ij;ϵ} = {(a_{1}, ⋯, a_{n}) ∈ E | a_{i} − a_{j} = ϵ}.

Encode a connected component C of E − ⋃_{\begin{matrix}1⩽i<j⩽n \\ ϵ∈\{0,1\} \end{matrix}} H_{ij;ϵ} by an [n]-sign type X = (X_{ij})_{i<j} as follows. Take any v = (a_{1}, ⋯, a_{n}) ∈ C. For any i, j, 1 ⩽ i < j ⩽ n, we set

X_{ij} = \{ \begin{matrix}+, & if a_{i} − a_{j} > 1; \\ −, & if a_{i} − a_{j} < 0; \\ ◯, & if 0 < a_{i} − a_{j} < 1. \end{matrix}

Then X is only dependent on C, but not on the choice of v in C. Identify C with X and call it a sign type.

Note that not all the [n]-sign types can be obtained in this way. Proposition 1.6. An [n]-sign type X = (X_{ij}) can be obtained in the above way if and only if \begin{matrix}X_{hm} \\ X_{hk} X_{km} \end{matrix} is one of the sign types (1)-(16) in Example 1.2 for any h < k < m in [n], and hence if and only if it is admissible. Proof. The first equivalence is a result of [8, 9]. The second equivalence follows directly from the definition of an admissible sign type by setting I = [n]. □

From this proposition, we see that the regular admissible sign types are in 1-1 correspondence with the Weyl chambers in E.

SIGN TYPES ASSOCIATED TO POSETS 7

1.7. Define a relation ≪ on the set D^{I} as below. Write X ≪ Y in D^{I}, if Y can be obtained from X by replacing some entries ◯ by the symbols +, −. In this case, we call Y an extension of X or call X a retraction of Y. This is a partial order relation on D^{I}. Clearly, a retraction of a dominant (resp. anti-dominant) sign type is again dominant (resp. anti-dominant). The maximal elements of D^{I} with respect to ≪ are regular sign types. There is a unique minimal element, called the trivial sign type, in D^{I} whose entries are all ◯. This is the unique element in D^{I} which is simultaneously dominant, anti-dominant and admissible. 1.8. By a digraph G, we mean a set V of vertices together with a set E of arrows, where an arrow of G is an ordered pair (x, y) with x, y ∈ V. Written G = (V, E). Say G is finite if |V | < ∞.

Two digraphs G = (V, E) and G′ = (V′, E′) are isomorphic, if there is a bijection ρ from V to V′ such that for any x, y ∈ V, (x, y) ∈ E if and only if (ρ(x), ρ(y)) ∈ E′.

To an I-sign type X = (X_{ij})_{i,j∈I}, we associate a digraph G_{X} = (V, E) by setting V = I and E = {(i, j) | X_{ij} = +}. Clearly, up to isomorphism, a digraph is associated to a sign type if and only if it is finite, contains no loops, no multiarrows and no length 2 direct circle, that is, it contains no arrow of the form (x, x) and contains at most one of the arrows (x, y), (y, x) for any x ≠ y in V. In this paper we shall always assume a digraph satisfying these conditions and identify it with the associated sign type.

Here and later, we use the concepts and the terminologies of the graph theory quite often. It is hard for us to provide all the initial definitions in the paper. We refer the readers to the book [14] as a dictionary. 1.9. Let S_{n} be the symmetric group on the set [n]. For any X = (X_{ij}) ∈ D^{[n]} and any w ∈ S_{n}, we set w(X) = (X_{w(i),w(j)}). This defines an action of S_{n} on D^{[n]}. Two sign types in D^{[n]} are in the same S_{n}-orbit if and only if their associated digraphs are isomorphic (see 1.8). The action of S_{n} respects the relation ≪ on D^{[n]} (see 1.7). So it fixes the trivial sign type and stabilizes the set D_{r}^{[n]} (see

8 JIAN-YI SHI

1.1). But it does not stabilize the set D_{a}^{[n]} (see 1.3 and Example 1.2). Then it is interesting to study the intersections of an S_{n}-orbit of D^{[n]} with the set D_{a}^{[n]} and with some subsets of D_{a}^{[n]}. We shall consider this in the subsequent sections.

§2. The set D_{p}^{I}. 2.1. To any X = (X_{ij}) ∈ D^{I}, define a relation ⩽_{X} on I as below. For i, j ∈ I, write i ⩽_{X} j if either i = j or X_{ij} = +.

Lemma 2.2. For X = (X_{ij}) ∈ D_{a}^{I}, the relation ⩽_{X} is a partial order on I.

Proof. We must show the following statements. For any i, j, k ∈ I, (a) i ⩽_{X} j and j ⩽_{X} k imply i ⩽_{X} k;

(b) i ⩽_{X} j and j ⩽_{X} i imply i = j.

First assume i ⩽_{X} j and j ⩽_{X} k. If either i = j or j = k holds, then the result i ⩽_{X} k is obvious. Now assume i ≠ j ≠ k. Then X_{ij} = X_{jk} = +. If (i, j, k) ∈ I_{c} (see 1.3), then we get X_{ik} = + by (1.3.2). If (i, j, k) ∉ I_{c}, then (k, j, i) ∈ I_{c}, and we have X_{kj} = X_{ji} = − by (1.1.1). Hence X_{ki} = − by (1.3.1) and X_{ik} = + by (1.1.1). So in either case, we have i ⩽_{X} k. (a) follows.

Under the assumption of (b), suppose i ≠ j. Then X_{ij} = X_{ji} = +, contradicting (1.1.1). So we must have i = j as required for (b). □

2.3. Note that not all the partial orders on I are associated to the admissible sign types as above. However, to a partial order ⪯ on I, we can associate a sign type Y = (Y_{ij}) with

(2.3.1)  Y_{ij} = \{ \begin{matrix}+, & if i ≺ j; \\ −, & if j ≺ i; \\ ◯, & if otherwise. \end{matrix}

Y is not always admissible, but admissible when ⪯ is a linear order (i.e. Y regular).

Lemma 2.4. Let Y be the sign type associated to a partial order ⪯ on I as above. If Y is regular, then Y is admissible.

SIGN TYPES ASSOCIATED TO POSETS 9

Proof. By (1.3.1) and (1.3.2), we can reduce ourselves to the case of I = [3]. From Example 1.2, we see that being regular, Y is associated to a partial order on [3] if and only if Y is admissible. □

2.5. We shall not distinguish between a partial order on I and the associated sign type.

Note that not all X ∈ D^{I} are associated to the partial orders on I. In Example 1.2, only the sign types (1)-(19) are associated to the partial orders on [3].

Let D_{p}^{I} be the set of all the sign types associated to the partial orders on I.

Lemma 2.6. X = (X_{ij}) ∈ D^{I} is in D_{p}^{I} if and only if for any triple i, j, k ∈ I, the relations X_{ij} = X_{jk} = χ ∈ {+, −} imply X_{ik} = χ.

Proof. Let ⩽_{X} be the relation on I associated to X. The implication “⟹”is amount to asserting that a partial order relation on I is transitive and so it is obvious. For the reversing implication, the given condition guarantees the transitivity of the relation ⩽_{X}. The remaining thing is to show that if i, j ∈ I satisfy both relations i ⩽_{X} j and j ⩽_{X} i then i = j. The relation i ⩽_{X} j (resp. j ⩽_{X} i) implies either i = j or X_{ij} = + (resp. either i = j or X_{ji} = +) holds. If i ≠ j then it would imply {X_{ij}, X_{ji}} = {+, +} , contradicting (1.1.1). Hence we must have i = j and so our result follows. □

Lemma 2.7. X = (X_{ij}) ∈ D_{p}^{I} is admissible if and only if

(2.7.1)  \begin{matrix}X_{ik} \\ X_{ij} X_{jk} \end{matrix} ∉ \{ −_{◯ ◯} , + ◯^{◯} , ◯ +^{◯} \}

for any (i, j, k) ∈ I_{c} (see 1.3).

Proof. This follows from (1.3.1), (1.3.2), Example 1.2, and the notices in 1.3 and 2.5. □

Corollary 2.8. (1) X ∈ D_{d̂}^{I} is in D_{p}^{I} if and only if for any i < j < k in I, the equations X_{ij} = X_{jk} = − imply X_{ik} = −.

10 JIAN-YI SHI

(2) X ∈ D_{p}^{I} ∩ D_{d̂}^{I} is in D_{a}^{I} if and only if for any i < j < k in I, the equation X_{ik} = − implies either X_{ij} = − or X_{jk} = −.

(3) X ∈ D_{d}^{I} is in D_{p}^{I} if and only if for any i < j < k in I, the equations X_{ij} = X_{jk} = + imply X_{ik} = +.

(4) X ∈ D_{d}^{I} is in D_{a}^{I} if and only if for any i < j < k in I, any of the equations X_{ij} = + and X_{jk} = + implies X_{ik} = +. Proof. (1) and (3) follow from Lemma 2.6. (2) and (4) are the consequence of Lemma 2.7. □

Note that in Corollary 2.8, we presuppose X ∈ D_{p}^{I} in (2), but not in (4). 2.9. Recall in 1.9 that we defined an action of S_{n} on the set D^{[n]}. When X ∈ D_{p}^{(n)}, we have also w(X) ∈ D_{p}^{[n]} by Lemma 2.6. So by restriction, we get an action of S_{n} on D_{p}^{[n]}. Proposition 2.10. (1) The set D_{ra}^{[n]} form a single simply-transitive S_{n}-orbit.

(2) The set D_{a}^{[n]} is stable under the cycle permutation (12 ⋯ n).

(3) Each S_{n}-orbit in D_{p}^{[n]} has non-empty intersections with both sets D_{d}^{[n]} and D_{d̂}^{[n]}.

(4) The S_{n}-orbits of D_{p}^{[n]} are in 1-1 correspondence with the isomorphic classes of the posets of size n. Proof. The regular admissible sign types are in 1-1 correspondence with the Weyl chambers in the euclidean space E. The action of S_{n} on D_{ra}^{[n]} coincides with that on the Weyl chambers, the latter is S_{n}-simply-transitive (see [1]). So we get (1). The assertion (2) was actually mentioned in 1.3, whose proof can be reduced to the case of n = 3, the latter is straightforward. The action of S_{n} respects the relation ≪ on D_{p}^{[n]} (see 1.7). We know that any sign type in D_{p}^{[n]} can be extended to a regular admissible sign type by Lemma 2.4, and that there is a (unique) regular admissible sign type which is dominant (resp. anti-dominant). We also know that a retraction of a dominant (resp. anti-dominant) sign type is again dominant

SIGN TYPES ASSOCIATED TO POSETS 11

(resp. anti-dominant). These facts, together with (1), implies (3). Finally, (4) is obvious. □

2.11. Example. In Example 1.2, there are seven S_{3}-orbits: {(1)}, {(4), (12), (15)}, {(5), (13), (16)}, {(6), (7), (8), (9), (10), (11)}, {(2), (3), (14), (17), (18), (19)}, {(20), (21), (22), (23), (24), (25)}, {(26), (27)}. The first three are also (123)-orbits. Each of the last four is divided into two (123)-orbits. In the fifth S_{3}-orbit, only one (123)-orbit is admissible. The first five S_{3}-orbits are in D_{p}^{[3]}, each of which contains some dominant and also some anti-dominant sign types. In particular, there is a unique dominant admissible sign type in each S_{3}-orbits of D_{p}^{[3]}. The last phenomenon only conditionally holds for an arbitrary n ∈ ℕ (see Theorem 5.2 for a precise statement).

§3. Poset graphs. 3.1. In 1.8, we associated a sign type to a digraph. A digraph associated to an element in D_{p}^{I} is called a poset graph. Thus by Lemma 2.6, a digraph G = (V, E) is a poset graph if and only if the following condition holds. (3.1.1) For any a, b, c ∈ V, the relations (a, b), (b, c) ∈ E imply (a, c) ∈ E.

In particular, this implies that a poset graph contains no direct circle by the fact that G contains no arrow of the form (x, x), x ∈ V (By a direct circle in G = (V, E), we mean a sequence of vertices v_{0}, v_{1}, ⋯, v_{t} = v_{0} in V with t ⩾ 3 such that v_{h} ≠ v_{k} for 1 ⩽ h < k ⩽ t, and that (v_{i−1}, v_{i}) ∈ E for 1 ⩽ i ⩽ t).

A digraph G = (V, E) satisfying the following property is called a Hasse graph. (3.1.2) For any a, b, c ∈ V, the relations (a, b), (b, c) ∈ E imply (a, c) ∉ E.

There is a natural 1-1 correspondence between poset graphs and Hasse graphs without direct circles (up to isomorphism). We shall identify a poset graph with the associated Hasse graph. In the remaining part of this section, we fix a poset graph G = (V, E). 3.2. A labeling of G = (V, E) is an injective map τ : V ⟶ ℕ. Denote G(τ) =

12 JIAN-YI SHI

(V, E, τ), and call it a labeled poset graph of G. Two labelings τ, η : V ⟶ ℕ are congruent, if there exists a digraph automorphism σ of G such that for any v, w ∈ V, we have τ(v) ⩽ τ(w) if and only if (ησ)(v) ⩽ (ησ)(w). A labeling τ is standard if the image im τ of τ is [n], where n = |V |.

Clearly, if two congruent labelings τ, η : V ⟶ ℕ satisfy im τ = im η, then there exists a digraph automorphism σ of G such that τ = ησ on V. In particular, this holds when τ and η are congruent standard labelings. 3.3. Let G(τ) be a labeled poset graph of G with I = im τ. We associate G(τ) to a sign type Z(G(τ)) = (Z_{ij})_{i,j∈I} such that for any i < j in I,

(3.3.1)  Z_{ij} = \{ \begin{matrix}+, & if (τ^{−1}(i), τ^{−1}(j)) ∈ E; \\ −, & if (τ^{−1}(j), τ^{−1}(i)) ∈ E; \\ ◯, & if otherwise. \end{matrix}

Recall in 1.8 that we associated any X ∈ D_{p}^{[n]} to a digraph G_{X} = ([n], E). Let τ : [n] ⟶ [n] be a labeling of G_{X} and let Z(G_{X}(τ)) be defined as above with I = [n]. Then by the definition, we see that X and Z(G_{X}(τ)) are in the same S_{n}- orbit of D_{p}^{[n]}. More precisely, regarding τ as an element of S_{n}, we have Z(G_{X}(τ)) = τ^{−1}(X).

The sign type Z(G(τ)) remains unchanged under any digraph automorphism of G in the following sense. Let σ : V ⟶ V be a bijection such that (a, b) ∈ E if and only if (σ(a), σ(b)) ∈ E for all a ≠ b in V. Let η = τσ. Then Z(G(τ)) = Z(G(η)). Lemma 3.4. Let τ, η : V ⟶ [n] be two standard labelings of G. Then Z(G(τ)) = Z(G(η)) if and only if τ and η are congruent. Proof. The discussion in 3.2 and 3.3 shows the implication “⟸”. For the reversing implication, let b_{i} = τ^{−1}(i) and c_{i} = η^{−1}(i) for all i, 1 ⩽ i ⩽ n. Then the map σ : b_{i} ⟶ c_{i} determines a digraph automorphism of G by (3.3.1) and the assumption Z(G(τ)) = Z(G(η)). Clearly, we have τ = ησ on V and hence τ and η are congruent. □

SIGN TYPES ASSOCIATED TO POSETS 13

3.5. Let (a, b) ∈ E. We say that τ is increasing (resp. decreasing) at (a, b), if τ(a) < τ(b) (resp. τ(b) < τ(a)). Clearly, Z(G(τ)) is dominant (resp. antidominant) if and only if τ is increasing (resp. decreasing) at all the arrows of G. We call τ an admissible (resp. dominant admissible, resp. anti-dominant admissible) labeling if Z(G(τ)) is an admissible (resp. dominant admissible, resp. anti-dominant admissible) sign type.

We shall use the abbreviations a.l., d.a.l. and d̂.a.l. for the terminologies admissible labeling, dominant admissible labeling and anti-dominant admissible labeling, respectively.

In a poset graph G = (V, E), two vertices v, w ∈ V are comparable if either (x, y) or (y, x) is in E, and incomparable if otherwise.

The following result gives some criteria for these labelings.

Lemma 3.6. Let G(τ) = (V, E, τ) be a labeled poset graph of G with I = im τ. (1) Z(G(τ)) ∈ D_{p}^{I}.

(2) τ is admissible if and only if for any triple a, b, c ∈ V with (a, b) ∈ E and c incomparable to both a, b in G, one of the following conditions holds. (i) τ(a) < τ(c) < τ(b), (ii) τ(c) > τ(a) > τ(b), (iii) τ(a) > τ(b) > τ(c).

(3) τ is dominant admissible if and only if τ is increasing at all the arrows of G, and the condition (2)(i) holds for any triple a, b, c ∈ V described in (2).

(4) τ is anti-dominant admissible if and only if τ is decreasing at all the arrows of G, and either of the conditions (ii), (iii) holds for any triple a, b, c ∈ V described in (2).

Proof. (1) holds since G is a poset graph. (2)-(4) are just the graph-theoretic versions of Lemma 2.7 and Corollary 2.8. □

3.7. We say that a poset graph G is admissible (resp. dominant admissible, resp. anti-dominant admissible) labelable, if there is a labeled poset graph of G whose associated sign type is admissible (resp. dominant admissible, resp. anti-dominant

14 JIAN-YI SHI

admissible).

We shall use the abbreviations a.ℓ., d.a.ℓ. and d̂.a.ℓ. for the terminologies admissible labelable, dominant admissible labelable and anti-dominant admissible labelable, respectively.

Note the difference between the abbreviations a.ℓ., a.d.ℓ., d̂.a.ℓ. here and a.l., a.d.l., d̂.a.l. in 3.5.

Let X ∈ D_{p}^{[n]} be with the associated poset graph G_{X}. Then that G_{X} is a.ℓ. (resp. d.a.ℓ., resp. d̂.a.ℓ.) is amount to that the S_{n}-orbit of D_{p}^{[n]} containing X contains an admissible (resp. dominant admissible, resp. anti-dominant admissible) sign type.

The following result is concerned with the relation of the labelability between a poset graph and its full subdigraphs.

Lemma 3.8. Let G = (V, E) be an a.ℓ. (resp. d.a.ℓ., resp. d̂.a.ℓ.) poset graph. Then any full subdigraph of G is also a.ℓ. (resp. d.a.ℓ., resp. d̂.a.ℓ.).

Proof. Obvious. □

§4. Geometry of D_{p}^{[n]}.

We gave a geometric interpretation in 1.5 for the admissible [n]-sign types. In the present section, we shall extend it to the elements of D_{p}^{[n]}. 4.1. Recall the notations E, H_{ij;ϵ} defined in 1.5. Let H = {H_{ij;ϵ} | 1 ⩽ i < j ⩽ n, ϵ = 0, 1}. Fix X = (X_{ij}) ∈ D_{p}^{[n]}. Let X = {Y ∈ D_{a}^{[n]} | X ≪ Y }. Define F_{X} ⊆ H as follows. For 1 ⩽ i < j ⩽ n, we designate H_{ij;1} (resp. H_{ij;0}) to F_{X} if and only if X_{ij} = + (resp. X_{ij} = −). Let E_{F_{X}} = E − ⋃_{H∈F_{X}} H.

Proposition 4.2. (1) X ≠ ∅; (2) All Y ∈ X fall into a single connected component C_{X} of E_{F_{X}};

(3) \overline{C}_{X} = \overline{⋃_{Y ∈X} Y}, which is convex in E, where \overline{C} is the closure of C under the ordinary topology in E.

SIGN TYPES ASSOCIATED TO POSETS 15

Proof. Any partial order on [n] can be extended to a linear order, and the latter is associated to a regular sign type which is admissible by Lemma 2.4. This implies (1). For (2), it suffices to show that for any H ∈ F_{X}, all Y ∈ X lie in the same side of H. But this follows from the definition of the set F_{X}. It remains to show (3). We have \overline{C}_{X} ⊇ \overline{⋃_{Y ∈X} Y} by (2). For the reversing inclusion, we have \overline{C}_{X} = \overline{C_{X} ⋂(E − (⋃_{H} H))}, where H ranges over H. So we need only to show the inclusion.

(4.2.1)  C_{X} ∩ (E − (⋃_{H} H)) ⊆ ⋃_{Y ∈X} Y.

Take any v = (a_{1}, ⋯, a_{n}) ∈ C_{X} ⋂(E − (⋃_{H} H)). Then for any i < j, we have a_{i} − a_{j} ≠ 0, 1; moreover, we have a_{i} − a_{j} > 1 if X_{ij} = +, and a_{i} − a_{j} < 0 if X_{ij} = −. Define a sign type Y = (Y_{ij})_{i<j} by

(4.2.2)  Y_{ij} = \{ \begin{matrix}+, & if a_{i} − a_{j} > 1; \\ −, & if a_{i} − a_{j} < 0; \\ ◯, & if 0 < a_{i} − a_{j} < 1. \end{matrix}

Then v ∈ Y and Y ∈ X. This shows (4.2.1) and hence the equation in (3) follows. The convexity of \overline{C}_{X} is obvious. □

4.3. Let C be the set of all the connected components of E_{F} with F ranging over the subsets of H.

From the above proposition, we see that π : X ⟶ C_{X} is a map from D_{p}^{[n]} to C.

One may ask if it is possible that two different elements of D_{p}^{[n]} give rise to the same element in C. The answer will be negative.

Note that if X ∈ D_{p}^{[n]} is not admissible, then by Lemma 2.7, there exist at least two pairs {i, j}, {h, k} ⊆ [n] with |{i, j} ∩ {h, k}| = 1 and X_{ij} = X_{hk} = ◯.

16 JIAN-YI SHI

Proposition 4.4. Let X = (X_{ij}) ∈ D_{p}^{[n]}. Suppose X_{ij} =◯ for some i ≠ j in [n]. Then for any χ ∈ Ξ (see 1.1), there is some Y ∈ X with Y_{ij} = χ. In particular, when χ ∈ {+, −}, we can choose Y to be regular.

Proof. Let P = {k ∈ [n] | k <_{X} i}, Q = {k ∈ [n] | i <_{X} k} and R = P ∪ Q ∪ {i}. Take a linear order extension of the partial order ⩽_{X} on R, say

a_{1}, ⋯, a_{α}, i, b_{1}, ⋯, b_{β},

where P = {a_{1}, ⋯, a_{α}} and Q = {b_{1}, ⋯, b_{β}}. Let T = [n] − R. Then j ∈ T. Moreover, with respect to ⩽_{X}, we have the following facts for any m ∈ T, p ∈ P and q ∈ Q.

(a) m and i are incomparable;

(b) If m and p are comparable, then p <_{X} m;

(c) If m and q are comparable, then m <_{X} q;

Take a linear order extension of the partial order ⩽_{X} on T, say

c_{1}, ⋯, c_{γ}, j, d_{1}, ⋯, d_{δ}.

Then by (a)-(c), both of the following orderings are linear order extensions of the partial order ⩽_{X} on [n].

a_{1}, ⋯, a_{α}, c_{1}, ⋯, c_{γ}, i, j, d_{1}, ⋯, d_{δ}, b_{1}, ⋯, b_{β}, (4.4.1) a_{1}, ⋯, a_{α}, c_{1}, ⋯, c_{γ}, j, i, d_{1}, ⋯, d_{δ}, b_{1}, ⋯, b_{β}. (4.4.2)

Let Y (resp. Z) be the sign type associated to the linear ordering (4.4.1) (resp. (4.4.2)) on [n]. Then we have Y, Z ∈ X with Y_{ij} = + and Z_{ij} = −. In particular, Y, Z are both regular. Let ⪯ be the relation on [n] obtained from the linear ordering (4.4.1) by forgetting the comparable relation between i and j. Then we see that ⪯ is a partial order on [n] which extends the relation ⩽_{X} and that the

SIGN TYPES ASSOCIATED TO POSETS 17

sign type W associated to ⪯ satisfies W_{ij} =◯. We also have W ∈ X by the notice in 4.3. This completes our proof. □

4.5. By a detailed observation of Example 1.2, we can see that for any X ∈ D^{[3]} − D_{p}^{[3]} (i.e. X is one of the sign types (20)-(27)), either X = ∅ (for X=(26), (27)), or there exists some i ≠ j in [3] with X_{ij} = ◯ such that {Y_{ij} | Y ∈ X } ⫋ Ξ (for the remaining X). This implies that the property of a sign type X stated in Proposition 4.4 distinguishes the elements of D_{p}^{[n]} from D^{[n]} − D_{p}^{[n]}. This still holds when [n] is replaced by any finite subset I ⊂ ℕ.

By Proposition 4.4, we get the following result.

Lemma 4.6. Let X ≠ X′ in D_{p}^{[n]}. Let X_{0} = {Y ∈ D_{ra}^{[n]} | X ≪ Y } and X′ = {Y ∈ D_{ra}^{[n]} | X′ ≪ Y }. Then X_{0} ≠ X′_{0}.

Proof. By Lemma 2.4, we have X_{0} ≠ ∅ ≠ X′_{0}. First assume that there exist some i ≠ j in [n] with X_{ij} = +, X′_{ij} = −. Then for any Y ∈ X_{0} and Y′ ∈ X′_{0}, we have Y_{ij} = + and Y′_{ij} = −. Next assume that there exist some i ≠ j in [n] with {X_{ij}, X′_{ij}} = {+,◯}. Without loss of generality, we may assume X_{ij} = + and X′_{ij} =◯. Then all Y ∈ X_{0} satisfy Y_{ij} = +. But by Proposition 4.4, there exists some Y′ ∈ X′_{0} with Y′_{ij} = −. Hence in either case, we have X_{0} ≠ X′_{0}. □

Theorem 4.7. (1) The map π : X ↦ C_{X} from D_{p}^{[n]} to C is injective.

(2) The image of π consists of all C ∈ C satisfying: for any i, j, 1 ⩽ i < j ⩽ n, exactly one of the following conditions holds.

(i) a_{i} − a_{j} > 1 for all (a_{1}, ⋯, a_{n}) ∈ C;

(ii) a_{i} − a_{j} < 0 for all (a_{1}, ⋯, a_{n}) ∈ C;

(iii) There exist some (a_{1}, ⋯, a_{n}), (b_{1}, ⋯, b_{n}), (c_{1}, ⋯, c_{n}) in C such that a_{i} − a_{j} > 1, b_{i} − b_{j} < 0 and 0 < c_{i} − c_{j} < 1.

Proof. (1) follows by Proposition 4.2, Lemma 4.6 and from the relation between F_{X} and C_{X}. Next we show (2). By Propositions 4.2 and 4.4, any C ∈ im π satisfies

18 JIAN-YI SHI

one of the conditions (i)-(iii) for any i, j, 1 ⩽ i < j ⩽ n. Conversely, suppose that C ∈ C satisfies these conditions. Define an [n]-sign type X = (X_{ij}) such that for any i, j, 1 ⩽ i < j ⩽ n,

(4.7.1)  X_{ij} = \{ \begin{matrix}+, & if a_{i} − a_{j} > 1 for all (a_{1}, ⋯, a_{n}) ∈ C, \\ −, & if a_{i} − a_{j} < 0 for all (a_{1}, ⋯, a_{n}) ∈ C, \\ ◯, & if otherwise. \end{matrix}

By Lemma 2.6, we can show X ∈ D_{p}^{[n]} by showing that X_{ij} = X_{jk} = ± imply X_{ik} = ± for any i, j, k ∈ [n], which is easy. Clearly, π(X) = C. □

§5. A graph-theoretic criterion for an S_{n}-orbit of D_{p}^{[n]} containing a dast.

In this section, we shall characterize a poset graphs to be d.a.ℓ. (see 3.7). This provides us a graph-theoretic criterion for an S_{n}-orbit of D_{p}^{[n]} containing a dast (see 0.4). We shall also show that each S_{n}-orbit of D_{p}^{[n]} contains at most one dast. 5.1. A poset graph is of type (A) (resp. (B)) if its associated Hasse graph is as below.

\begin{matrix}∘—→∘ \\ ∘—→∘ \end{matrix}  (resp.  \begin{matrix}∘—→∘—→∘ \\ ∘ \end{matrix} ) .

A poset graph is A-avoiding (resp. B-avoiding), if it contains no full subdigraph of type A (resp. B). A poset graph is nice, if it is both A- and B-avoidings.

Theorem 5.2. (1) A poset graph is d.a.ℓ. if and only if it is nice.

(2) A poset graph has at most one d.a.l. (up to congruence, see 3.5 and 3.2).

(3) Each S_{n}-orbit of D_{p}^{[n]} contains at most one dast, exactly one if and only if the corresponding poset graph is nice.

5.3. In a poset graph G = (V, E), we associate to any x ∈ V two vertex sets X_{x} = {z ∈ V | (z, x) ∈ E} and Y_{x} = {z ∈ V | (x, z) ∈ E}. It is clear that for any (x, y) ∈ E, we have X_{x} ⫋ X_{y} and Y_{y} ⫋ Y_{x}.

a, b ∈ V are associated in G, if both equations X_{a} = X_{b} and Y_{a} = Y_{b} hold. Clearly, a, b ∈ V are associated if and only if the map ϕ : V ↦ V defined by

(5.3.1)  ϕ(x) = \{ \begin{matrix}x, & if x ≠ a, b; \\ a, & if x = b; \\ b, & if x = a. \end{matrix}

determines a digraph automorphism of G.

Lemma 5.4. Let G = (V, E) be a nice poset graph with |V | = n and let a, b, c ∈ V be pairwisely different.

(1) Either X_{a} ⊆ X_{b} or X_{b} ⊆ X_{a} holds. Also, either Y_{a} ⊆ Y_{b} or Y_{b} ⊆ Y_{a} holds.

(2) If X_{b} ⫋ X_{a}, then Y_{a} ⊆ Y_{b}.

(3) If X_{a} ⫋ X_{b}, let c ∈ X_{b} − X_{a}, then X_{c} ⊆ X_{a}.

(4) Suppose that X_{a} ⊆ X_{b} ⊆ X_{c} and Y_{a} ⊇ Y_{b} ⊇ Y_{c}. If either (a, b) ∈ E or (b, c) ∈ E holds, then (a, c) ∈ E.

Proof. Assertion (1) is obvious in the case where a, b are comparable (see 3.5). When a, b are incomparable, this follows by the condition that G is A-avoiding.

(2) and (3) hold since G is B-avoiding. It remains to show (4). If (a, b) ∈ E, then a ∈ X_{b} ⊆ X_{c} and hence (a, c) ∈ E. If (b, c) ∈ E, then c ∈ Y_{b} ⊆ Y_{a}, which implies (a, c) ∈ E also. □

5.5. Now assume that G = (V, E) is a nice poset graph with V = {a_{1}, a_{2}, ⋯, a_{n}}. Then by Lemma 5.4 (1),(2), there is a permutation i_{1}, i_{2}, ⋯, i_{n} of 1, 2, ⋯, n such that

(5.5.1)  \begin{matrix}X_{a_{i_{1}}} ⊆ X_{a_{i_{2}}} ⊆ ⋯ ⊆ X_{a_{in}}; \\ Y_{a_{i_{1}}} ⊇ Y_{a_{i_{2}}} ⊇ ⋯ ⊇ Y_{a_{in}} . \end{matrix}

If there is another permutation j_{1}, j_{2}, ⋯, j_{n} of 1, 2, ⋯, n satisfies (5.5.1) with the subscripts i_{k} replaced by j_{k} for all k, 1 ⩽ k ⩽ n, then the sequence a_{j_{1}}, ⋯, a_{j_{n}} can be obtained from a_{i_{1}}, ⋯, a_{i_{n}} by permuting some associated terms (see 5.3).

20 JIAN-YI SHI

Lemma 5.6. Suppose that a poset graph G = (V, E) is nice with V = {a_{1}, ⋯, a_{n}} such that

(5.6.1)  \begin{matrix}X_{a_{1}} ⊆ X_{a_{2}} ⊆ ⋯ ⊆ X_{a_{n}}; \\ Y_{a_{1}} ⊇ Y_{a_{2}} ⊇ ⋯ ⊇ Y_{a_{n}}. \end{matrix}

Then τ : a_{i} ↦ i is a d.a.l. of G (see 3.5). Proof. For any (a_{i}, a_{j}) ∈ E, we have X_{a_{i}} ⫋ X_{a_{j}} and so i < j by (5.6.1). This means that τ is increasing at all the arrows of G (see 3.5). So by 3.5, τ is a dominant labeling. By Corollary 2.8 (4), to show τ admissible, it suffices to show that for any i < j < k in [n], any of the conditions (a_{i}, a_{j}) ∈ E and (a_{j}, a_{k}) ∈ E implies (a_{i}, a_{k}) ∈ E. But this follows from Lemma 5.4 (4). □ Lemma 5.7. Let G = (V, E) be a nice poset graph with τ : V ⟶ [n] a d.a.l.

(1) If a, b ∈ V satisfy either X_{a} ⫋ X_{b}, Y_{a} ⊇ Y_{b}, or X_{a} ⊆ X_{b}, Y_{a} ⫌ Y_{b}, then τ(a) < τ(b).

(2) Let a_{i} = τ^{−1}(i) for all i ∈ [n]. Then V = {a_{1}, ⋯, a_{n}} satisfies the conditions (5.6.1). Proof. (1) First assume X_{a} ⫋ X_{b} and Y_{a} ⊇ Y_{b}. Let c ∈ X_{b} − X_{a}. Then we have (c, b) ∈ E and (c, a) ∉ E. We also have (b, a) ∉ E by the fact X_{b} ⊈ X_{a}. Suppose τ(a) > τ(b). Since τ is a dominant labeling and G is a poset graph, we have (a, b), (a, c) ∉ E. That is, a is incomparable with both b, c. Since τ is a d.a.l. and (c, b) ∈ E, we have τ(c) < τ(a) < τ(b) by Lemma 3.6 (3). This gives rise to a contradiction. So we must have τ(a) < τ(b). The case X_{a} ⊆ X_{b} and Y_{a} ⫌ Y_{b} can be argued similarly.

(2) We must show X_{a_{i}} ⊆ X_{a_{j}} and Y_{a_{i}} ⊇ Y_{a_{j}} for any i < j in [n]. Suppose not. Then by Lemma 5.4 (1), (2), it would imply X_{a_{j}} ⊆ X_{a_{i}}, Y_{a_{j}} ⊇ Y_{a_{i}} and not both equal for some i < j in [n], contradicting (1). This implies (2). □ Proof of Theorem 5.2. (1) The implication “⟸ ”follows from Lemmas 5.4 and 5.6. For the reversing implication, it suffices to show by Lemma 3.8 that a poset

SIGN TYPES ASSOCIATED TO POSETS 21

graph G = (V, E) of type (A) or (B) has no d.a.l. Suppose not. Let τ be a d.a.l. of G. If G is of type (A) with V = {a, b, c, d} and E = {(a, b), (c, d)}, then by Lemma 3.6 (3), we have both τ(a) < τ(c) < τ(b) and τ(c) < τ(b) < τ(d). If G is of type (B) with V = {a, b, c, d} and E = {(a, b), (a, c), (b, c)}, then by Lemma 3.6 (3), we have both τ(a) < τ(d) < τ(b) and τ(b) < τ(d) < τ(c). This gives rise to a contradiction in either case. (1) is proved.

(2) Suppose that there are two d.a.l.’s τ, η : V ⟶ ℕ. Let b_{i} = τ^{−1}(i) and c_{i} = η^{−1}(i) for all i ∈ [n]. Then by Lemma 5.7 (2), we have the relations (5.6.1) with a_{i}, i ∈ [n], replaced all by b_{i} or all by c_{i}. By 5.5, we see that the sequence c_{1}, ⋯, c_{n} can be obtained from b_{1}, ⋯, b_{n} by permuting some associated terms. That is, there is a digraph automorphism σ of G such that σ(b_{i}) = c_{i} for all i ∈ [n]. So τ = ησ and hence τ and η are congruent (see 3.2).

(3) This follows from (1), (2) and Lemma 3.4. □

§6. Admirability of posets associated to dasts.

In the present section, we shall show that a poset (I, ⩽_{X}) associated to an I-dast X is admirable (see 6.2 for the definition). 6.1. Let (P, ⪯) be a poset. By a chain of P, we mean a subset J of P such that either i ≺ j or j ≺ i holds for any i ≠ j in J. A chain of P can be expressed as a sequence J : a_{1}, ⋯, a_{r} with a_{1} ≺ ⋯ ≺ a_{r}. Note that we allow a chain to be an empty set. By a k-chain-family in P (k ⩾ 1), we mean a subset J of P which is a disjoint union of k chains J_{i} (1 ⩽ i ⩽ k). We usually write J = J_{1} ∪ ⋯ ∪ J_{k}, and call it a decomposition form (or d.f. for short) of a k-chain-family J.

Let (I, ⩽_{X}) be a poset associated to a sign type X ∈ D_{p}^{I}. Then the chains (regarded as subsets) of I are precisely all the subsets I′ ⊆ I with (X_{ij})_{i,j∈I′} regular by Lemma 2.4. 6.2. Let d_{k} (k ⩾ 1) be the maximal possible cardinality of a k-chain-family in P. Then d_{1} < d_{2} < ⋯ < d_{r} = n = |P | for some r ⩾ 1. Let λ_{1} = d_{1}, λ_{i} = d_{i} − d_{i−1}

22 JIAN-YI SHI

for 1 < i ⩽ r. Then λ_{1} ⩾ λ_{2} ⩾ ⋯ ⩾ λ_{r} by a theorem of C. Greene (see [4]). We get a partition λ = (λ_{1}, ⋯, λ_{r}) of n, called the partition associated to the poset P.

Note that there does not always exist an r-chain-family P = J_{1} ∪ ⋯ ∪ J_{r} with |J_{i}| = λ_{i}, 1 ⩽ i ⩽ r for the poset P. A poset P is admirable if there does exist such an r-chain-family. The admirable posets play an important role in the combinatorics and in the group theory (see [7, 8, 10] for example). 6.3. Now take a poset to be a finite subset I of ℕ with the partial order ⩽_{X} determined by an I-dast X = (X_{ij}) (see 2.1). In the subsequent discussion, an I-dast X is fixed. So by the poset I, we always refer to the partial order ⩽_{X}. Let λ = (λ_{1}, ⋯, λ_{r}) be the partition of n = |I| associated to this poset.

We have the following result concerning the relations between two orders ⩽_{X} and ⩽ on I which will be useful in the subsequent discussion.

Lemma 6.4. X ∈ D^{I} is an I-dast if and only if it satisfies the following two conditions.

(1) For any i, j ∈ I, the relation i <_{X} j implies i < j, i.e. the relation ⩽ on I is a linear order extension of the partial order ⩽_{X}.

(2) If i, j, k ∈ I satisfy i < j ⩽ k (resp. k ⩽ i < j), then the relation i <_{X} j implies i <_{X} k (resp. k <_{X} j).

Proof. It is easily seen that X ∈ D^{I} is dominant if and only if X satisfies condition (1). By Corollary 2.8 (4), we also see that X ∈ D_{d}^{I} is admissible if and only if X satisfies condition (2). Then our result follows from these two facts. □

6.5. We can define a lexicographic order ⪯_{1} on the set Δ_{1}(I, X) of all the chains in I as follows. Let ξ : a_{1}, ⋯, a_{r} and ξ′ : a′_{1}, ⋯, a′_{t} be in Δ_{1}(I, X). We write ξ ≺_{1} ξ′, if there exists some i ⩾ 1 such that a_{j} = a′_{j} for all j < i, and a_{i} < a′_{i}, with the convention that a_{h} = a′_{m} = max{i | i ∈ I} for all h > r and m > t. By this definition, we see that if ξ′ is a proper subchain of a chain ξ, then ξ ≺_{1} ξ′.

SIGN TYPES ASSOCIATED TO POSETS 23

Furthermore, we can also define a lexicographic order ⪯_{k} on the set Δ_{k}(I, X) of all the d.f.’s (see 6.1) of the k-chain-families of I (k ⩾ 1) as below. We write ξ_{1} ∪ ⋯ ∪ ξ_{k} ≺_{k} ξ′_{1} ∪ ⋯ ∪ ξ′_{k} in Δ_{k}(I, X). if there exists some i ⩾ 1 such that ξ_{j} = ξ′_{j} for all j < i, and ξ_{i} ≺_{1} ξ′_{i}. A d.f.

(6.5.1)  ξ = ξ_{1} ∪ ⋯ ∪ ξ_{k}

of a k-chain-family ξ in I is standard, if it is minimal among all the d.f.’s of ξ with respect to ⪯_{k}. Clearly, a standard d.f. (or s.d.f. for brevity) (6.5.1) of a k-chain-family ξ uniquely exists and satisfies

(6.5.2)  ξ_{1} ≺_{1} ⋯ ≺_{1} ξ_{k}.

6.6. For any k ⩾ 1, we define a k-chain-family

(6.6.1)  I^{k} = I_{1}^{k} ∪ I_{2}^{k} ∪ ⋯ ∪ I_{k}^{k}

in the poset (I, ⩽_{X}) as follows. Let i, 1 ⩽ i ⩽ k. Suppose that we have got all the chains I_{j}^{k}, j < i. Let E_{i} = I − (⋃_{j<i}I_{j}^{k}). We want to find a chain

(6.6.2)  I_{i}^{k} : a_{i1}, a_{i2}, ⋯, a_{im_{i}}

from the subposet (E_{i}, ⩽_{X}). We set I_{i}^{k} = ∅ if E_{i} = ∅. Otherwise, we take a_{i1} to be the smallest number in E_{i}. Inductively, having got a_{ij} for some j ⩾ 1, we either take a_{i,j+1} to be the smallest number h in E_{i} with h > a_{ij} and X_{a_{ij},h} = + whenever it exists, or set m_{i} = j if otherwise.

We see that the expression (6.6.1) just obtained is the s.d.f. of a k-chain-family in I. We can even show that (6.6.1) is minimal in the set Δ_{k}(I, X) with respect to ⪯_{k}. There is some r ⩾ 1 such that I_{r}^{r} ≠ ∅ and ∑_{i=1}^{r} |I_{i}^{r}| = n. By our construction, we see that for any h, k with 1 ⩽ h ⩽ k, the chain I_{h}^{k} in the k-chain-family (6.6.1) is only dependent on the poset (I, ⩽_{X}), but not on the choice of k. So we may denote I_{h}^{k} simply by I_{h} and call (6.6.1) the s.d.f. of the canonical k-chain-family of I for any k ⩾ 1.

24 JIAN-YI SHI

Theorem 6.7. Let λ = (λ_{1}, ⋯, λ_{r}) be the partition associated to the poset (I, ⩽_{X} ). Then for any k, 1 ⩽ k ⩽ r, the s.d.f. I^{k} = I_{1} ∪⋯∪I_{k} of the canonical k-chain-family in I satisfies λ_{i} = |I_{i}| for 1 ⩽ i ⩽ k.

To show the theorem, we need a lemma. Let m_{I} be the smallest number in I.

Lemma 6.8. For any k ⩾ 1, there is a k-chain-family of the s.d.f.

(6.8.1)  J = J_{1} ∪ ⋯ ∪ J_{k}

in I with |J| = λ_{1} + ⋯ + λ_{k} and J_{1} = I_{1}. In particular, we have |I_{1}| = λ_{1}.

Proof. Suppose that

(6.8.2)  K = K_{1} ∪ ⋯ ∪ K_{k}

is the s.d.f. of a k-chain-family in I of the cardinality λ_{1} + ⋯ + λ_{k}, where

(6.8.3)  K_{i} : b_{i1}, ⋯, b_{ip_{i}}  (1 ⩽ i ⩽ k).

(i) First we claim m_{1} ⩾ p_{1}. Suppose not. Then m_{1} < p_{1}. Note a_{11} = m_{I}. So there exists some j, 1 ⩽ j < p_{1}, such that the half-closed interval (b_{1j}, b_{1,j+1}] contains no a_{1i}, 1 ⩽ i ⩽ m_{1}. Also, there exists some s satisfying a_{1s} ⩽ b_{1j}. Take s largest possible with this property. Then a_{1s} <_{X} b_{1,j+1} by the fact b_{1j} <_{X} b_{1,j+1} and by Lemma 6.4. Hence s < m_{1} by the choice of the chain I_{1}. So we have a_{1s} <_{X} b_{1,j+1} < a_{1,s+1}, contradicting the choice of a_{1,s+1}.

(ii) Next we claim a_{1i} ⩽ b_{1i} for all i ⩽ p_{1}. For otherwise, there is some j with a_{1j} > b_{1j}. Then j > 1 as a_{11} = m_{I}. Take j smallest possible with this property. Then a_{1h} ⩽ b_{1h} for all h < j. Now a_{1,j−1} ⩽ b_{1,j−1} <_{X} b_{1j} < a_{1j} and hence a_{1,j−1} <_{X} b_{1j} by Lemma 6.4, contradicting the choice of a_{1j}.

(iii) Now we are ready to show the first part of the lemma. If K_{1} = I_{1}, then there is nothing to do. If K_{1} ≠ I_{1}, then one of the following two cases must occur.

SIGN TYPES ASSOCIATED TO POSETS 25

(a) K_{1} : a_{11}, ⋯, a_{1p_{1}} with p_{1} ≨ m_{1};

(b) There is some m ⩽ p_{1} with a_{1m} ≠ b_{1m}.

In the case (a), let K′_{1} = I_{1} and K′_{i} = K_{i} − {a_{1j} | p_{1} < j ⩽ m_{1}} for all i > 1. Then K′ = K′_{1} ∪ ⋯ ∪ K′_{k} is a k-chain-family of the cardinality not less than |K|, Hence |K′| = |K| by the maximality assumption on K. So K′ = K′_{1} ∪ ⋯ ∪ K′_{k} is the s.d.f. of a required k-chain-family after possibly renumbering the chains K′_{2}, ⋯, K′_{k} if necessary. Next assume the case (b). Take m as small as possible with this property. Then a_{1h} = b_{1h} for all h < m. We have a_{1m} < b_{1m} by (ii) . If a_{1m} ∉ K, then let K′_{1} = (K_{1} − {b_{1m}}) ⋃{a_{1m}} and K′_{h} = K_{h} for 1 < h ⩽ k. If a_{1m} ∈ K, say a_{1m} = b_{ij} for some i, j, then i > 1. Let K′_{1} : a_{11}, ⋯, a_{1m}, b_{i,j+1}, ⋯, b_{i,p_{i}}, let K′_{i} : b_{i1}, ⋯, b_{i,j−1}, b_{1m}, ⋯, b_{1,p_{1}}, and let K′_{h} = K_{h} for h ≠ i, 1 < h ⩽ k. Then in either case, K′ = K′_{1} ∪ ⋯ ∪ K′_{k} is the s.d.f. of a k-chain-family in I with |K′| = |K| after possibly renumbering the chains K′_{2}, ⋯, K′_{k} if necessary. Applying reversing induction on g(K) ⩽ m_{1} and noting g(K′) > g(K), we can eventually get the s.d.f. of a k-chain-family of I to be either a required one or the one in the case (a). This completes the proof for the first assertion of the lemma. The second assertion follows by taking k = 1. □

6.9. Proof of Theorem 6.7. By Lemma 6.8, we have |I_{1}| = λ_{1} and that for any k ⩾ 1, there is the s.d.f.

(6.9.1)  J = J_{1} ∪ ⋯ ∪ J_{k}

of a k-chain-family in the poset (I, ⩽_{X}) with |J| = λ_{1} + ⋯ + λ_{k} and J_{1} = I_{1}. Let L = I −I_{1}. Take the submatrix X^{L} = (X_{ij})_{i,j∈L} of X. Then X^{L} is an L-dast. The partial order relation ⩽_{X^{L}} on L associated to X^{L} coincides with the one obtained by restriction to L of ⩽_{X}. This implies that the partition associated to the poset (L, ⩽_{X^{L}}) is λ′ = (λ_{2}, λ_{3}, ⋯, λ_{r}) by noting that J_{2} ∪ ⋯ ∪ J_{k} is a k-chain-family in L with the maximal possible cardinality λ_{2} + ⋯ + λ_{k} for any k > 1. Therefore our result follows by applying induction on n = |I| ⩾ 1. □

Acknowledgement.

I would like to express my deep gratitude to Professor Gus Lehrer and Dr.

Bob Howlett for their arranging me to visit Australia as an ARC Senoir Research

Associate, and to School of Mathematics and Statistics, Sydney University for the

hospitality during my writing of this paper.

References

1. N. Bourbaki, Groupes et algèbres de Lie, Ch. 4-6, Hermann, Paris, 1968.

2. Christos A. Athanasiadis, A class of labeled posets and the Shi arrangement of hyperplanes, to appear in J. Comb. Thy (ser. A) (1997).

3. Christos A. Athanasiadis and Svante Linusson, A simple bijection for the regions of the Shi arrangement of hyperplanes, MSRI preprint no. 1997-020 (1997).

4. C.Greene and D. J. Kleitman, The structure of Sperner k-families, J. Comb. Theory (A) 20 (1976), 41-68.

5. P.Headley, Reduced expressions in infinite Coxeter groups, Ph.D. thesis, Univ. of Michigan, Ann Arbor (1994).

6. P.Headley, On reduced expressions in affine Weyl groups, FPSAC’94, May 23-27, 1994, DIMACS preprint, Formal Power Series and Algebraic Combinatorics, pp. 225-232.

7. V. Ostrik, preprint.

8. Jian-yi Shi, The Kazhdan-Lusztig cells in certain affine Weyl groups, Lect. Notes in Math. vol.1179, Springer-Verlag, 1986.

9. Jian-yi Shi, Sign types corresponding to an affine Weyl group, J. London Math. Soc. 35(2) (1987), 56-74.

10. Jian-yi Shi, The generalized Robinson-Schensted algorithm on the affine Weyl group of type Ã_{n−1}, J. Algebra 139 (1991), 364-394.

11. Jian-yi Shi, The number of ⊕ -sign types, Quart. J. Math., Oxford (2) 48 (1997), 93-105.

12. R. Stanley, Hyperplane arrangements, interval orders, and trees, Proc. Natl. Acad. Sci. USA 93 (1996), 2620-2625.

13. R. Stanley, Hyperplane arrangements, parking functions and tree inversions, preprint (1996).

14. K. Thulasiraman and M. N. S. Swamy, Graphs: Theory and Algorithms, John Wiley & Sons, Inc., 1992.