Printer Friendly

Intervals and factors in the Bruhat order.

The interval structure of the Bruhat order on the symmetric group is not well understood. One reason for this is that, sometimes, even those intervals that are isomorphic to principal order ideals are actually making use of the fact that a reduced word for the minimum element in the interval can be formed by deleting an arbitrary subword of symbols from a reduced word of the maximum element in the interval. The purpose of this paper is to gain a better understanding of that phenomenon. More precisely, we explore the principal order ideals [[LAMBDA].sub.w] with the property that whenever [x, y] is isomorphic to [[LAMBDA].sub.w], one May obtain a reduced word for x by deleting a consecutive subword from a reduced word for y. Note that deletion of some subword will always produce a reduced word for x, but not necessarily the deletion of a consecutive one. The possibility for a consecutive such word is what we highlight in this work, and what we refer to as "forcing" a factor, as defined in Definition 2.7. Structural analyses of intervals and principal order ideals are of particular interest because it follows from [2] that the Kazhdan-Lusztig polynomial corresponding to the interval [x, y] depends only on the principal order ideal [[LAMBDA].sub.y].

The precise question we answer here is laid out in Section 1, along with the relevant objects and examples. Section 2 gives additional definitions, and the main results appear in Theorems 3.4 and 4.10. Finally, Section 5 discusses directions for subsequent work.

1 Introduction

The symmetric group [G.sub.n] on {1, ..., n} is generated by {[s.sub.1], ..., [s.sub.n-1]}, where [s.sub.i] is the permutation interchanging i and i + 1, and fixing all other elements. These generators, known as simple reflections, satisfy the Coxeter relations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A permutation w can be recorded as a product of simple reflections

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

of which there are infinitely many representations, or written uniquely in one-line notation

w = w(1)w(2) ... w(n).

These two representations of the same class of objects are quite different, and each have advantages in certain contexts. The main result of [10] was a way to translate between the two options.

The order in which we compose maps indicates that s^w interchanges the positions of the values i and i + 1 in the one-line notation of w, and ws* interchanges the values in positions i and i + 1 in the one-line notation of w.

Example 1.1 The permutation w [member of] [G.sub.4] which maps 1 to 3, 2 to itself, 3 to 4, and 4 to 1, would be written [member of] one-line notation as

w = 3241.

A few of the infinite many ways to express w as a product of simple reflections include:

w = [s.sub.1] [s.sub.2] [s.sub.1] [s.sub.3] = [s.sub.2] [s.sub.1] [s.sub.2] [s.sub.3] = [s.sub.1] [s.sub.2] [s.sub.3] [s.sub.1] = [s.sub.1] [s.sub.3] [s.sub.3] [s.sub.2][s.sub.3][s.sub.1].

As demonstrated in Example 1.1, the number of simple reflections involved in representing a particular permutation is not fixed. There is, however, a minimum value.

Definition 1.2 If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where l(w) is minimal, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a reduced decomposition of w, and the string of subscripts [i.sub.1] ... [i.sub.l(w)] is a reduced word of w. The set of reduced words of w is denoted R(w). The nonnegative integer l(w) is the length of w.

To avoid confusion with permutations, which are also strings of integers, reduced words and their symbols will be written in sans serif.

The Coxeter relations among the symbols in a reduced decomposition have obvious analogues for the symbols in a reduced word:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A product of simple reflections is reduced if it is a reduced decomposition for some permutation, and a string of integers is reduced if the corresponding product of simple reflections is reduced.

Example 1.3 Continuing Example 1.1, l(3241) = 4 and R(3241) = {1213,2123,1231}. (Note that we have not explained how to compute these values.)

The Bruhat order is a partial ordering given to the elements of a Coxeter group. Although we are only concerned with the symmetric group, we give the full definition here.

Definition 1.4 Suppose that x and y are elements of a Coxeter group. Then x [less than or equal to] y in the Bruhat order if there exists a reduced word of x that can be obtained from a reduced word of y by deleting symbols and simplifying Coxeter relations as necessary.

The Bruhat order gives a graded poset structure to any Coxeter group, where the rank of an element is the element's length. The Bruhat order of [G.sub.4] is depicted in Figure 1. Of course, Definition 1.4 can be stated analogously in terms of reduced decompositions.

The Bruhat order gives a partial ordering to the permutations of a given set. Another way to describe it is as a subword order on reduced decompositions/words. Dyer studied intervals in the Bruhat order for all finite Coxeter groups, showing that there are only finitely many non-isomorphic intervals of any given length [3]. Jantzen and Hultman have classified all possible length 4 intervals, as well as the length 5 intervals in the symmetric group [4, 5, 6]. The special class of intervals for which the minimal element is the identity, known as principal order ideals and defined formally in Definition 2.3, were studied by the author in [9]. As is obvious from Table 1, there are intervals in [G.sub.n] that never appear as principal order ideals.

Example 1.5 The interval [2143,4231] in the Bruhat order of [G.sub.4], depicted in Figure 2, never appears as a principal order ideal in the Bruhat order of any symmetric group.

The purpose of this paper is to explore how and when generic intervals in [G.sub.n] might be isomorphic to principal order ideals. So that we can refer to it subsequently, we highlight the following discussion in a remark.

Remark 1.6 Principal order ideals in [G.sub.n] are special cases of intervals, and they lack a certain freedom that more general intervals possess. In the Bruhat order, x [less than or equal to] y if there is an element of R(x) that is a subword of an element of R(y). In a principal order ideal, this x is the identity permutation, and so R(x) = {0}. Of course 0 is a subword of every word. Thus, for principal order ideals, the entire reduced word for y must be deleted in order to yield the reduced word for x. In particular, note that what is getting deleted is a consecutive subword (in fact, the entire word itself). On the other hand, in a generic interval, what gets deleted from the reduced word for y need not be a consecutive subword. This potential yields some generic intervals that do not appear as principal order ideals.

Example 1.7 The interval [21543,52341] is isomorphic to the interval in Figure 2. Note that R(21543) = {1343, 3143, 3413, 3431,1434, 4134,4314, 4341}

and

R(52341) ={1234321,1243421,1423421,4123421,1243241,1423241,4123241 1243214,1423214, 4123214,1432341,4132341, 4312341,1432314, 4132314, 4312314,1432134,4132134,4312134, 4321234}.

Thus no element of R(21543) can be obtained by deleting a consecutive subword of symbols from an element of R(52341).

The purpose of the current work is to examine when a principal order ideal in the symmetric group also appears as a more general interval. In particular, we want to understand when such an interval, not necessarily beginning at rank 0 in the poset, must still come from deleting a factor from a reduced word of its maximum element.

Before making this property precise, consider the following result, where vexillary permutations are exactly those that avoid the pattern 2143.

In [10], we showed that if a permutation w contains a vexillary p-pattern, then there is a reduced word for w possessing a reduced word f for p as a factor, possibly with a fixed positive integer added to each letter in f. If v is the permutation obtained by deleting this subword from w, then this implies that the interval [v, w] in the Bruhat order would be isomorphic to [[LAMBDA].sub.p], the principal order ideal for p. Indeed, this would also imply that there is a copy of [[LAMBDA].sub.p] sitting as a principal order ideal inside of the principal order ideal [[LAMBDA].sub.w] of w, as depicted in Figure 3.

Example 1.8 The permutation 4213 contains the vexillary pattern 321. The interval [1243,4213] and the principal order ideal [[LAMBDA].sub.3214] are both isomorphic to [[LAMBDA].sub.321], as shown in Figure 4.

We are now able to clarify the main question of this paper: when does a principal order ideal [[LAMBDA].sub.w] [subset or equal to] [G.sub.n] have the property that for all intervals [x, y] [congruent to] [[LAMBDA].sub.w], there is a reduced word i [member of] R(x) and a reduced word j [member of] R(y) such that i can be formed by deleting a consecutive subword from j?

The main results of this paper are that no decomposable permutation can force a factor (Theorem 3.4), and that the permutation n(n - 1) ... 321 does force a factor for all n (Theorem 4.10). These are preceded by a discussion of the useful terminology in Section 2, and the paper concludes with suggestions for future work.

2 Definitions

We now define the main objects of the current work. More details and background information about Coxeter groups can be found in [1] and [7].

Two of the most fundamental structural features of a poset are its intervals and its order ideals. In a poset with a unique minimal element, these objects intersect at the concept of a principal order ideal.

Definition 2.1 Consider a poset P and elements x,y [member of] P with x [less than or equal to] y. The set of elements {z [less than or equal to] x [less than or equal to] z [less than or equal to] y} [subset not equal to] P is denoted [x, y], and is called an interval.

Definition 2.2 An order ideal in a poset P is a subset I [subset not equal to] P such that if y [member of] I and x [less than or equal to] y, then x [member of] I.

Definition 2.3 A principal order ideal in a poset P is an order ideal with a unique maximal element. Equivalently, the principal order ideals of P are the subsets [[LAMBDA].sub.y] = {z : z [subset not equal to] y} for each y [member of] P. If P has a unique minimal element [??], then the principal order ideals are exactly the intervals of the form [0, y].

To calculate the length of a permutation, we must make a preliminary definition.

Definition 2.4 Given a permutation w, an inversion in w is a pair (i,j) such that i < j and w(i) > w(j).

Inversions are easy to see in the one-line notation of a permutation: they consist of a value (the w(i) of the definition) appearing somewhere to the left of a smaller value (the w(j) of the definition). It is well known that l(w) is equal to the number of inversions in w, and it is now clear that there is a unique permutation in [G.sub.n] having maximal length.

Definition 2.5 Fix a positive integer n. The unique element of maximal length in [G.sub.n] is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

As described in Definition 1.4, the relation x [less than or equal to] y in the Bruhat order allows any subset of symbols to be deleted from a reduced word of y in order to form a reduced word of x. In particular, these symbols need not be consecutive. For example, as shown in Figure 1,

1324 = [S.sub.2] < [S.sub.1][S.sub.2][S.sub.3] = 2341.

In this paper, we will examine when all of the activity happening within an interval [x, y] in the Bruhat order of some symmetric group is actually happening within some consecutive substring of the symbols of an element of R(y), all of which must be deleted to form an element of R(x).

Definition 2.6 A factor in a word is a consecutive substring.

This paper is concerned with understanding when intervals [x, y] that are isomorphic to [[LAMBDA].sub.w] for some w May or May not be formed in "interesting" ways. This is made more precise in the following definition.

Definition 2.7 Fix an element w [member of] [G.sub.n], and consider its principal order ideal [[LAMBDA].sub.w]. If it is true that for every interval [x,y] [congruent to] [[LAMBDA].sub.w], there exists an element of R(x) formed by deleting a factor from an element of R(y), then w forces a factor. Otherwise w does not force a factor.

The "interesting" feature noted above was described in Remark 1.6 in the introduction to this work. The first thing to note about this topic is that determining which permutations force a factor is an interesting problem. More precisely, not all permutations do so.

Example 2.8 Consider [[lambda].sub.2314] [subset] [G.sub.4]. Note that the principal order ideal [[LAMBDA].sub.2314] is isomorphic to the interval [1324,2341].

However, there is no element of R(1324) = {2} that can be formed from by deleting a single factor from an element of R(2341) = {123}. Thus 2314 = [s.sub.1][s.sub.2] does not force a factor.

3 Permutations that do not force a factor

In this section we describe a large class of permutations that do not force a factor.

Definition 3.1 A permutation w is decomposable if [[LAMBDA].sub.w] [congruent to][[LAMBDA].sub.u]x [[lambda].sub.v], where neither[[LAMBDA].sub.u] nor [[LAMBDA].sub.v] is itself isomorphic to [[LAMBDA].sub.w]. If w is not decomposable, then it is indecomposable.

Example 3.2 The permutation 4213 [member of] [G.sub.4] is decomposable because [[LAMBDA].sub.4213] = [[LAMBDA].sub.3214] x [[LAMBDA].sub.1234]. This is depicted in Figure 4.

Proposition 3.3 ([8]) A permutation w [member of] [G.sub.n] is decomposable if and only if there exists m [member of] [n - 2] and a reduced word [a.sub.1][a.sub.2] [member of] R(w), where [a.sub.1] and [a.sub.2] are nonempty, such that a; consists only of letters less than or equal to m, and [a.sub.3-i] consists only of letters strictly greater than m.

Example 3.2 continued. The reduced words of 4213 [member of] [G.sub.4] are {3121, 3212, 1321}. Then in the language of Proposition 3.3, we can let m = 2, and [a.sub.1] = 3 and [a.sub.2] = 121. Thus 4213 is decomposable.

We now show, constructively, that no decomposable permutation forces a factor. This means that for any decomposable permutation w, we must produce an interval [x, y] [congruent to] [[LAMBDA].sub.w] such that no reduced word for x can be obtained by deleting a factor from any reduced word for y.

Theorem 3.4 If w is decomposable, then w does not force a factor.

Proof: Suppose that w is decomposable. Consider the value m and the reduced word [a.sub.1][a.sub.2] [member of] R(w) guaranteed by Proposition 3.3. We can assume, without loss of generality, that i =1 in the proposition. Let [k.sub.1] [less than or equal to] m be the largest value appearing in [a.sub.1], and [k.sub.2] [greater than or equal to] m + 1 be the smallest value appearing in [a.sub.2]. Let [a'.sub.2] be the string obtained from [a.sub.2] by increasing each symbol by 1. Also, define

b = ([k.sub.1] + 1)([k.sub.1] + 2) ... (m + 1) ... ([k.sub.2] - 1) [k.sub.2],

a string of consecutive increasing letters. Now define [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; that is,

b [member of] R([w.sup.-])

It is not hard to see that [a.sub.1]b[a'.sub.2] is reduced, by construction. Define [w.sup.+] so that

[a.sub.1]b[a'.sub.2] [member of] R([w.sup.+]).

It is not hard to see that

[[LAMBDA].sub.w] [congruent to] [[w.sup.-], [w.sup.+]].

Neither [a.sub.1] nor [a'.sub.2] contain any of the letters {[k.sub.1] + 1, [k.sub.1] + 2, ..., [k.sub.2]}. Moreover, [k.sub.1] [member of] [a.sub.1] and [k.sub.2] + 1 [member of] [a'.sub.2]. Thus the Coxeter relations prohibit [k.sub.1] [member of] [a.sub.1] from commuting into or across b from the left, and similarly [k.sub.2] + 1 [member of] [a'.sub.2] cannot do so from the right. Thus it will be impossible to get [k.sub.1] and [k.sub.2] + 1 into the same factor whose deletion would yield b.

Therefore w does not force a factor. []

Example 2.8 depicts the procedure outlined in Theorem 3.4. In that case, w = [s.sub.1][s.sub.2] = 2314, and so m =1, [a.sub.1] = 1, and [a.sub.2] = 2. Then [k.sub.1] = 1 and [k.sub.2] = 2, and so [a'.sub.2] = 3 and the resulting string [a.sub.1]b[a'.sub.2] = 123.

Therefore [w.sup.-] = [s.sub.2] = 1324 and [w.sup.+] = [s.sub.1][s.sub.2][s.sub.3] = 2341. This yields exactly the demonstrative interval [1324, 2341] of the example.

Theorem 3.4 s[[LAMBDA].sub.y]s that if a permutation has a principal order ideal that can decompose nontrivially into a direct product of posets, then there are ways for that principal order ideal to appear as an interval in an "interesting" way, as described in Remark 1.6. In this context, then, the result May not be surprising. It might even be natural to wonder whether the converse to Theorem 3.4 is also true. Unfortunately, it is not.

Example 3.5 Consider the permutation w = 3412 = [s.sub.2][s.sub.1][s.sub.3][s.sub.2] [member of] [G.sub.4]. Because R(w) = {2132, 2312}, we see that this w is indecomposable. It is not hard to check that

[12543, 52341] [congruent to] [[LAMBDA].sub.3412].

To show that w does not force a factor, note that R(12543) = {343,434}, and recall R(52341) from Example 1.7. There is no element of R(52341) from which a single factor could be deleted to yield either 343 or 434. Thus w does not force a factor

4 Permutations that do force a factor

In this section we prove that the longest permutation n(n - 1) ... 321 always forces a factor. With the understanding that the symmetric group is given a poset under the Bruhat order, we will abuse notation slightly and write [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], henceforth. Thus we now show that for any interval [x, y] appearing in the Bruhat order of a symmetric group satisfying [x, y] [congruent to] [G.sub.n], there exists some i [member of] R(x) that can be obtained from some j [member of] R(y) by deleting a factor.

The main result will be proved inductively, and its proof will benefit from some preliminary results. The first of these is about generic intervals in the Bruhat order of the symmetric group, not of any fixed isomorphism class. The proposition concerns the coatoms in an interval [x, y], that is, the elements w of the interval that are covered by y (denoted x [less than or equal to] w [??] y).

Proposition 4.1 Suppose that x,y [member of] [G.sub.n] with x < y. Fix i satisfying x(i) [not equal to] y(i). Then there exists a permutation w with x [less than or equal to] w [??] y and w(i) [not equal to] y(i).

Proof: We prove the result by induction on l(y) - l(x).

If l(y) - l(x) = 1, then set w = x. Now consider l(y) - l(x) > 1, and suppose inductively that the result is true for all intervals of length less than l(y) - l(x).

Fix some v satisfying x [less than or equal to] v [??] y. If v(i) [not equal to] y(i), then set w = v and we are done. If, instead, v(i) = y(i), then we can apply the inductive assumption to the interval [x, v]. This yields a permutation u with x [less than or equal to] u [??] v and u(i) [not equal to] v(i). Consider the interval [u, y]. As described in Table 1, this has only one possible form, and includes a fourth element which will denote w.

Because l(y) - l(u) = 2, the permutations u and y differ, as strings, in either three or four positions, one of which is necessarily position i.

If u and y differ in four positions, then u and v differ in two positions (i and j, for some j), and v and y differ in two other positions. The two transpositions commute, and so w is obtained from y by swapping the values in positions i and j. In other words, w(i) [not equal to] y(i).

Suppose, on the other hand, that u and y differ in just three positions: i, [j.sub.1], and [j.sub.2]. Then, because v(i) = y(i), we have that v and y differ in positions [j.sub.1] and [j.sub.2]. Because w [not equal to] v, the two positions in which w and y differ, which must be a subset {i, [j.sub.1], [j.sub.2]}, cannot be both [j.sub.1] and [j.sub.2]. Thus, one of them must be i, meaning that w(i) [not equal to] y(i). []

We now focus on a particular kind of interval in the symmetric group, and look at what such an interval implies for the reduced words of its minimum and maximum elements.

Definition 4.2 Let s be a string of integers, and t [member of] Z. The shift of s by t is the string s1 obtained by adding t to each of the values in s.

Example 4.3 [(5 -10).sup.4] = 9 3 4 and [(5 - 10).sup.-4] = 1 - 5 - 4.

Proposition 4.4 Fix a positive integer k. Suppose that x, y [member of] [G.sub.n] have reduced words ac [member of] R(x) and abc [member of] R(y), and that [x, y] [congruent to] [G.sub.k]. Then there exists an integer t [less than or equal to] 0 such that [b.sup.-t] [member of] R([w.sup.k.sub.0]).

Proof: The length of b is equal to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Because b is a reduced word, it cannot contain fewer than k - 1 distinct symbols. Moreover, if it were to contain more than k - 1 distinct symbols, then [x, y] would not be isomorphic to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus b contains exactly k - 1 distinct symbols. In order to form a reduced word of length l([w.sup.k.sub.0]) out of k - 1 distinct symbols, that reduced word must actually be the shift by t of a reduced word for [w.sup.k.sub.0], where t + 1 be the smallest symbol in b. []

Example 4.5 In the language of Proposition 4.4, let x = 21534 and y = 24531, with reduced words 143 [member of] R(x) and 123243 [member of] R(y). The interval [x, y] [subset] [G.sub.5] is isomorphic to [S.sub.3], as drawn in Figure 5. In this example, t = 1 because [232.sup.-1] [member of] R(321).

The next two propositions require an additional definition.

Definition 4.6 Fix a string s. Consider a monotonic substring s' of s with smallest value a and largest value b (the endpoints of the monotonic substring). This s' is thin if no value c [member of] s', with a < c < b, appears between a and b in s.

Example 4.7 Let s = 91402365. The monotonic substring 0235 is thin, while the monotonic substring 910 is not thin because of the 4 appearing between 9 and 0 in s.

Proposition 4.8 Fix a positive integer k. Suppose that x, y [member of] [G.sub.n] have reduced words ac [member of] R(x) and abc [member of] R(y), with [b.sup.-t] [member of] R([w.sup.k.sub.0]) for some integer t [greater than or equal to] 0. Then x and y, as strings, are identical outside of a thin monotonic substring oflength k, which appears in increasing order in x and decreasing order in y.

To ease the discussion, we will call this monotonic substring that distinguishes x from y the swap-string. Note that if k is odd, then x and y will also be identical in the central position of the swap-string.

Proof: We prove the result by induction on the length of a.

If a = 0, then

y = (12 ... t(t + k) ... (t + 2)(t + 1))x.

Thus x and y only differ, as strings, in the subsequence involving {t + 1, ..., t + k}, which necessarily appears in increasing order in x (because bc is reduced, so multiplying c by the permutation corresponding to b cannot undo any inversions) and decreasing order in y. Because there are no values between t + 1 and t + k that are not already in the swap-string, the result holds.

Now suppose that a = ua' where u is a single letter. Let x' = [s.sub.u]x and y' = [s.sub.u]y, and assume inductively that the result holds for a'c [member of] R(x') and a'bc [member of] R(y'). This means that the strings x' and y' are identical except for a substring of length k whose values appear in increasing order in x' and decreasing order in y', and these swap-strings are thin.

Because ac and abc are both reduced words, the value u must appear to the left of u +1 in both x' and y'. Thus at most one of {u, u+1} appears in the swap-string for x' and y', so swapping the positions of the two values cannot change the monotonicity of the differentiating substrings. In other words, lengthening the prefix might change the specific values that differ in the two strings, but cannot alter the swap-string phenomenon.

Similarly, the thinness of the swap-string is maintained by this operation. []

The converse to Proposition 4.8 is also true. Its proof is similar to the main result of [10], and we offer the broad strokes of it here.

Proposition 4.9 Suppose that x, y [member of] [G.sub.n] are identical, as strings, outside of a thin monotonic substring of length k, which appears in increasing order in x and decreasing order in y. Then there exist reduced words ac [member of] R(x) and abc [member of] R(y), with [b.sup.-t] [member of] R([w.sup.k.sub.0]) for some integer t [right arrow] 0.

Proof: We will transform both x and y into the identity permutation, by minimally many simple reflections, thus obtaining reduced words for each.

Look for any values sitting in between the endpoints of the swap-string that are not actually in the swap-string themselves. Because the swap-strings are thin, each of these values is either smaller than the minimum value of the swap-string or larger than the maximum value of the swap-string. Identically multiply x and y on the right by a succession of simple reflections (thus swapping the values in adjacent positions in the strings) to move all of the too-large (respectively, too-small) values to the right (respectively, left) of the swap-string. The order in which these values are moved can be chosen so that each multiplication removes exactly one inversion. Let C be the reduced word corresponding to the product of these multiplied simple reflections.

We now have two permutations x' [less than or equal to] x and y' [less than or equal to] y that are identical, as strings, outside of a swap-string of length k, which appears in increasing order in x' and decreasing order in y'. Moreover, the swap-string is a factor in each of x' and y'. We can now multiply y' on the right by a succession of simple reflections, each of which removes exactly one inversion from the permutation, to put this decreasing factor into increasing order and thus yield x'. This will correspond to a reduced word b. Moreover, b necessarily satisfies [b.sup.-t] [member of] R([w.sup.k.sub.0]), where the leftmost symbol in the swap-string appears in the (t - 1)st position. Fix some a [member of] R(x').

Let c be the string obtained by writing C in reverse order. Then ac [member of] R(x) and abc [member of] R(y), with [b.sup.-t] [member of] R([w.sup.k.sub.0]) for some integer t [greater than or equal to] 0, as desired. []

We are now able to prove the main result of this section, describing a family of permutations that force factors.

Theorem 4.10 For all integers n > 1, the permutation [w.sup.n.sub.0] = n(n - 1) ... 321 forces a factor.

Proof: First note that [[LAMBDA].sub.21] [congruent to] [G.sub.2] is the following poset.

If [x, y] [congruent to] [G.sub.2], then l(y) = l(x) + 1, and so a reduced word for x must be obtained from a reduced word for y by deleting a single letter. A single letter is necessarily a factor, and so the result holds for n = 2. Now consider some integer n > 2, and suppose, inductively, that the result holds for [W.sup.n-1.sub.0].

Let [x, y] [member of] [G.sub.m] be an interval that is isomorphic to [G.sub.n]. In [G.sub.n], there are two intervals

[23 ... n1, [w.sup.n.sub.0]] and [n12 *** (n - 1), [w.sup.n.sub.0]], (1)

each of which is isomorphic to [G.sub.n-1]. Thus, there must be two such intervals [[x.sub.1], y] and [[x.sub.2], y] in [x, y]. Recall the results of Propositions 4.4 and 4.8. Let the swap-string for [[x.sub.i], y] [congruent to] [G.sub.n- 1] have values [h.sup.(i).sub.1] < ... < [h.sup.(i).sup.n-1].

Because [[x.sub.1], y] and [[x.sub.2], y] overlap extensively in [x, y], as do the intervals of (1) in [G.sub.n], their respective swap-strings must share many values. In particular, at the second highest rank in [x, y], the intervals [[x.sub.1], y] and [[x.sub.2], y] overlap in n - 3 elements. Thus the two swap-strings share n - 2 values. It remains to determine how these two swap-strings could fit together. In order to satisfy the thinness condition for the swap-string of [[x.sup.i], y], the n - 2 shared values must be either {[h.sup.(i).sub.1], ..., [h.sup.(i).sub.n-2]} or {[h.sup.(i).sub.2], ..., [h.sup.(i).sub.n-1]}.

Note that [[x.sub.1], y] [union] [[x.sub.2], y] includes all of the coatoms of [x, y]. By Proposition 4.1, x and y cannot differ in any positions outside the union of the two swap-strings. This union encompasses exactly n positions. Because the swap-strings are thin, and because l(y) - l(x) = l([w.sup.n.sub.0]), we must have the n positions form an increasing substring in x and a decreasing substring in y, and these two monotonic substrings must be thin in their respective permutations. Proposition 4.9 now implies that some i [member of] R(x) can be obtained from some j [member of] R(y) by deleting a factor, completing the proof. []

To illustrate the proof of Theorem 4.10, we present the following example.

Example 4.11 Let x = 321456 and y = 361542 in [G.sub.6], for which [x, y] [congruent to] [G.sub.4]. In the language of the proof of Theorem 4.10, then, n = 4. Let [x.sub.1] = 341562 and [x.sub.2] = 361245. For i [member of] {1,2}, the interval [[x.sub.i], y] [subset] [x, y] is isomorphic to [G.sub.3], as depicted in Figure 6. Note that these intervals share 4 - 3 = 1 coatom (thepermutation 361452 [member of] [G.sub.6]), and the swap-string {4, 5, 6} for [[x.sub.1], y] shares 4 - 2 = 2 values with the swap-string {2,4,5} for [[x.sub.2], y].

In fact, Proposition 4.9 also tells us the form of the factor forced by wg.

Corollary 4.12 For all integers n > 1, if [x, y] [congruent to] [G.sub.n], then some i [member of] R(x) can be obtained from some j [member of] R(y) by deleting a factor b, where [b.sup.t] [member of] R([w.sup.n.sub.0]) for some t [member of] Z.

5 Open questions

We have now documented a family of permutations that do not force factors and a second family of permutations that do force factors. Completely characterizing those permutations that do (or do not) force factors is still an open question, and one which could shed significant light on the interval structure of the Bruhat order for the symmetric group.

In a different direction, the present work studies only the finite Coxeter group of type A, although the analogous question can be asked for Coxeter groups of other types as well.

Acknowledgements

I am grateful for the thoughtful suggestions of an anonymous referee.

References

[1] A. Bjomer and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics 231, Springer, New York, 2005.

[2] F. Brenti, A combinatorial formula for Kazhdan-Lusztig polynomials, Invent. Math. 118 (1994), 371-394.

[3] M. J. Dyer, On the "Bruhat graph" of a Coxeter system, Compos. Math. 78 (1991), 185-191.

[4] A. Hultman, Bruhat intervals of length 4 in Weyl groups, J. Combin. Theory, Ser. A 102 (2003), 163-178.

[5] A. Hultman, Combinatorial complexes, Bruhat intervals and reflection distances, Ph.D. thesis, KTH, 2003.

[6] J. C. Jantzen, Moduln mit Einem Hochsten Gewicht, Lecture Notes in Mathematics 750, Springer-Verlag, Berlin, 1979.

[7] I. G. Macdonald, Notes on Schubert Polynomials, Laboratoire de combinatoire et d'informatique mathematique (LACIM), Universite du Quebec a Montreal, Montreal, 1991.

[8] B. E. Tenner, The combinatorics of reduced decompositions, Ph.D. thesis, MIT, 2006.

[9] B. E. Tenner, Pattern avoidance and the Bruhat order, J. Combin. Theory Ser. A 114 (2007), 888-905.

[10] B. E. Tenner, Reduced decompositions and permutation patterns, J. Algebraic Combin. 24 (2006), 263-284.

Bridget Eileen Tenner *

Department of Mathematical Sciences, DePaul University, USA

* Research partially supported by a DePaul University Competitive Research Leave grant and a Simons Foundation Collaboration Grant for Mathematicians.

received 10th June 2014, accepted 20th May 2015.

Tab. 1: The number of non-isomorphic intervals and principals order
ideals of length at most 5 (as defined in Definition 1.2) appearing
in the Bruhat order of symmetric groups.

Length                               0   1   2   3   4    5

# Non-isomorphic intervals           1   1   1   3   7   25
in [G.sub.n]

# Non-isomorphic principal order     1   1   1   2   3    5
ideals in [G.sub.n]
COPYRIGHT 2015 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Tenner, Bridget Eileen
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Date:Jan 1, 2015
Words:6064
Previous Article:Avoider-enforcer star games.
Next Article:A randomized algorithm for finding a maximum clique in the visibility graph of a simple polygon.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters