# Combinatorial realization of the Hopf algebra of sashes.

1 Introduction

The focus of this research is on combinatorial Hopf algebras: Hopf algebras such that the basis elements of the underlying vector space are indexed by a family of combinatorial objects. For each n [greater than or equal to] 0, let [O.sub.n] be a finite set of "combinatorial objects". We define a graded vector space over a field K, such that for each grade n the basis vectors of the vector space are indexed by the elements of [O.sub.n]. That is, the graded vector space is: K[[O.sub.[infinity]]] = [[direct sum].sub.n[greater than or equal to]0] K[[O.sub.n]]. For simplicity, we refer to a basis element of this vector space by the combinatorial object indexing it. There is a more sophisticated approach for defining combinatorial Hopf algebras. For more information see [1].

Let [S.sub.n] be the group of permutations of the set of the first n integers [n] = {1, 2,..., n}. Also define [n, n'] = {n, n + 1, ..., n'} for n' [greater than or equal to] n. For x = [x.sub.1][x.sub.2] ... [x.sub.n] [member of] [S.sub.n], an inversion of x is a pair ([x.sub.i], [x.sub.j]) where i < j and [x.sub.i] > [x.sub.j], and the inversion set of x is the set of all such inversions. The weak order is the partial order on [S.sub.n] with x [less than or equal to] x' if and only if the inversion set of x is contained in the inversion set of x'. The weak order is a lattice. The inverse [x.sup.-1] of a permutation x [member of] [S.sub.n] is the permutation [x.sup.~1] = y = [y.sub.1] ... [y.sub.n] [member of] Sn [s.sub.uch] that [y.sub.i] = j when [x.sub.j] = i.

Let T be a set consisting of integers [t.sub.1] < [t.sub.2] < ... < [t.sub.n]. Given a permutation x [member of] [S.sub.n], the notation [(x).sub.T] stands for the permutation of T whose one-line notation has [t.sub.j] in the [i.sup.th] position when [x.sub.i] = j. On the other hand, given a permutation x of T, the standardization, st(x), is the unique permutation y [member of] [S.sub.n] such that [(y).sub.T] = x.

Now let T be a subset of [n]. For x [member of] [S.sup.n], the permutation x[|.sub.T] is the permutation of T obtained by removing from the one-line notation for x all entries that are not elements of T.

Example 1.1. Let x = 31254, [T.sub.1] = {2,3,6, 8, 9}, and [T.sub.2] = {2, 3, 5}. Then, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and thus st(62398) = 31254. Also, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The Malvenuto-Reutenauer Hopf algebra MR is a graded Hopf Algebra (K[[S.sub.[infinity]]], *, [delta]). Let K[[S.sub.[infinity]]] = [[direct sum].sub.n[greater than or equal to]0] K[[S.sub.n]] be a graded vector space. Let x = [x.sub.1][x.sub.2] ... [x.sub.1][x.sub.2] [x.sub.p] [member of] [S.sub.p] and y = [y.sub.1][y.sub.2] ... [y.sub.q] [member of] [S.sub.q]. Define y' = [y'.sub.1] ... [y'.sub.q] to be [(y).sub.[p+1,p+q]] so that [y'.sub.i] = [y.sub.i] + p. A shifted shuffle of x and y' is a permutation z [member of] [S.sub.n] where n = p + q, z[|.sub.[p]] = x and Z [|.sub.[p+1,n]] = y'. From [3], the product of x and y in MR is the sum of all the shifted shuffles of x and y. Equivalently,

x x y = [SIGMA][x x y', y' x x] (1)

where x x y' is the concatenation of the permutations x and y', and [SIGMA][x x y', y' x x] denotes the sum of all the elements in the weak order interval [x x y', y' x x]. The poset induced on [S.sub.n] by the weak order is a lattice (also denoted by [S.sub.n]). The coproduct in MR is:

[DELTA](x) = [p.summation over (i=0)] st([x.sub.1] ... [x.sub.i]) [cross product] st([x.sub.i+1] ... [x.sub.p]) (2)

where st([x.sub.1] ... [x.sub.0]) and st([x.sub.p+1] ... [x.sub.p]) are both interpreted as the empty permutation [empty set].

Define the map Inv: [S.sub.n] [right arrow] [S.sub.n] by Inv(x) = [x.sup.-1] and extend the map linearly to a map Inv: K[S.sub.[infinity]] [right arrow] K[S.sub.[infinity]]. MR is known to be self dual [4] and specifically Inv is an isomorphism from (K[[S.sub.[infinity]]], *, [DELTA]) to the graded dual Hopf algebra (K [[S.sub.[infinity]]], [[DELTA].sup.*], [m.sup.*]). Let x [member of] [S.sub.q], y [member of] [S.sub.q], and z e [S.sub.n], where p + q = n. Given a subset T of p elements of [n], TC denotes the complement of T in [n]. The dual product is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

and the dual coproduct is:

[m.sup.*](z) = (Inv [cross product] Inv)([DELTA]([z.sup.-1]) = [n.summation over (i=0)] z[|.sub.[i]] [cross product] st(z[|.sub.[i+1,n]]) (4)

where z[|.sub.[0]] and z[|.sub.[n+i,n]] are both interpreted as the empty permutation [empty set].

Now that we have explicitly described both the Hopf algebra of permutations and the dual Hopf algebra of permutations, we will present a family of Hopf subalgebras that are defined by a particular patternavoidance condition. We give more detail on the particular pattern-avoidance condition below, but in general the condition requires patterns of length k to have k and 1 adjacent. This family of Hopf algebras is defined by Reading [5].

For some k [greater than or equal to] 2, let V [subset or equal to] [2, k - 1] such that [absolute value of V] = j and let [V.sup.C] be the complement of V in [2, k - 1]. A permutation x [member of] [S.sub.n] avoids the pattern V(k1) [V.sup.C] if for every subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of x with [j.sub.+2] = [i.sub.j+1] + 1, the standardization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not of the form [upsilon](k1)[upsilon]' for any permutation v of the set V and any permutation [upsilon]' of [V.sup.C]. In the notation of Babson and Steingrimsson [2] avoiding V (k1) [V.sup.C] means avoiding all patterns of the form [[upsilon].sub.1] - ... - [[upsilon].sub.j] - k1 - [[upsilon]'.sub.1] - ... - [[upsilon]'.sub.k-j-2], where [[upsilon].sub.1] ... [[upsilon].sub.j] is a permutation of V and [[upsilon]'.sub.1] .. [[upsilon]'.sub.k-j-2] is a permutation of [V.sup.C].

Let U be a set of patterns of the form V(k1)[V.sup.C], where [absolute value of V] and k can vary. Define [Av.sub.n] to be the set of permutations in [S.sub.n] that avoid all of the patterns in U. We define a graded Hopf algebra (K[[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]) as a graded Hopf subalgebra of MR. Let K[[Av.sub.n]] be a vector space, over a field K, with basis vectors indexed by the elements of [Av.sub.n], and let K[[Av.sub.[infinity]]] be the graded vector space [direct sum].sub.n[greater than or equal to]0] K[[Av.sub.n]]. The product and coproduct on K[[Av.sub.[infinity]]] are described below.

We define a map [[pi].sub.[down arrow]]: [S.sub.n] [right arrow] [Av.sub.n] recursively. If x [member of] [Av.sub.n] then define [[pi].sub.[down arrow]](x) = x. If x [member of] [S.sub.n], but x [not member of] [Av.sub.n], then x contains an instance of a pattern V(k1) [V.sup.C] in U. That is, there exists some subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of x, where [i.sub.j+2] = [i.sub.j+1] + 1 and j = [absolute value of V], such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some permutations [upsilon] and [upsilon]' of V and [V.sup.C]. Exchange [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in x to create a new permutation x', calculate [n.sub.[down arrow]](x') recursively and set [n.sub.[down arrow]] (x) = [n.sub.[down arrow]] (x'). The recursion must terminate because an inversion of x is destroyed at every step, and because the identity permutation is in [Av.sub.n]. The map [n.sub.[down arrow]], is well-defined as explained in [5, Remark 9.5]. We emphasize that the definition of [n.sub.[down arrow]], is dependent on U.

The map [n.sub.[down arrow]] defines an equivalence relation with permutations x, x' [member of] [S.sub.n] equivalent if and only if [n.sub.[down arrow]] (x) = [n.sub.[down arrow]] (x'). The set [Av.sub.n] is a set of representatives of these equivalence classes. This equivalence relation is a lattice congruence on the weak order. Therefore the poset induced on [Av.sub.n] by the weak order is a lattice (also denoted by [Av.sub.n]) and the map [n.sub.[down arrow]] is a lattice homomorphism from the weak order to [Av.sub.n]. The congruence classes defined by [n.sub.[down arrow]] are intervals, and [n.sub.[down arrow]] maps an element to the minimal element of its congruence class. Let [n.sub.[up arrow]] be the map that takes an element to the maximal element of its congruence class.

The following proposition is a special case of [5, Proposition 2.2]. The congruence on [S.sub.n] defined by [n.sub.[down arrow]], is denoted by [THETA]. For x [member of] [S.sub.n], the congruence class of x mod [THETA] is denoted by [[x].sub.[THETA]].

Proposition 1.2. Given [S.sub.n] a finite lattice, [THETA] a congruence on [S.sub.n], and x [member of] [S.sub.n], the map y [right arrow] [[y].sub.[THETA]] restricts to a one-to-one correspondence between elements of [S.sub.n] covered by [n.sub.[down arrow]] (x) and elements of [Av.sub.n] covered by [[x].sub.[THETA]].

Both [n.sub.[down arrow]], and [n.sub.[up arrow]] are order preserving and [n.sub.[up arrow]] x [n.sub.[down arrow]] = [n.sub.[up arrow]] and [n.sub.[down arrow]] x [n.sub.[up arrow]] = [n.sub.[down arrow]]. A [n.sub.[down arrow]]-move is the result of switching two adjacent entries of a permutation in the manner described above. That is, it changes ... k1 ... to ... 1k ... for some pattern in U. A [n.sub.[up arrow]]-move is the result of switching two adjacent entries of a permutation in a way such that a [n.sub.[up arrow]]-move undoes a [n.sub.[down arrow]]-move. That is, it changes ... 1k ... to ... k1 ....

We define a map r: K[[S.sub.[infinity]]] [right arrow] K[[Av.sub.[infinity]]] that identifies the representative of a congruence class. Given

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly, we define a map c: K[[Av.sub.[infinity]]] [right arrow] K[[S.sub.[infinity]]] that takes an avoider to the sum of its congruence class:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now describe the product and coproduct in (K [[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]). Let x [member of] [Av.sub.p], and let y [member of] [Av.sub.q]. Then:

[m.sub.Av](x [cross product] y) = x[*.sub.Av] y = r(x x y). (5)

Just as the product in MR is [SIGMA][x x y', y' x x|, we can view this product as:

x [*.sub.Av] y = [SIGMA][x x y', [n.sub.[down arrow]](y' x x)], (6)

where [x x y', [n.sub.[down arrow]] (y' x x)] is an interval on the lattice [Av.sub.n].

The coproduct is:

[[DELTA].sub.av](z) = (r [cross product] r) ([DELTA](c(z))). (7)

We now describe the Hopf algebra (K[[Av.sub.[infinity]]], [[DELTA].sup.*.sub.Av], [*.sup.*.sub.Av]) that is dual to (K[[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]). We extend the map [n.sub.[down arrow]] linearly, so [n.sub.[down arrow]] is a map from K[[S.sub.[infinity]]] to K[[Av.sub.[infinity]]]. The map that is dual to the map c is [c.sup.*]: K[[S.sub.[infinity]]] [right arrow] K[[Av.sub.[infinity]]], where [c.sup.*](x) = [n.sub.[down arrow]] (x) for x [member of] K[[S.sub.[infinity]]]. The map that is dual to the map r is [r.sup.*]: K[[Av.sub.[infinity]]] [right arrow] K[[S.sub.[infinity]]], where [r.sup.*](x) = x for x [member of] K[[Av.sub.[infinity]]].

Let z [member of] [Av.sub.n], where n = p + q. The dual coproduct is given by dualizing Equation (5), so that:

[m.sup.*.sub.Av](z) = [m.sup.*](z). (8)

The dual product [[DELTA].sup.*.sub.Av] is given by dualizing Equation (7):

[[DELTA].sup.*.sub.Av](x [cross product] y) = [n.sub.[down arrow]] [[DELTA].sup.*](x [cross product] y). (9)

Combining Equation (9) with Equation (3), we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

Equation (10) leads to the following order theoretic description of the coproduct [[DELTA].sub.Av], which was worked out jointly with Nathan Reading.

Given z [member of] [Av.sub.n], a subset T [subset or equal to] [n] is good with respect to z if there exists a permutation z' = [z'.sub.1] ... [z'.sub.n] with [n.sub.[down arrow]](z') = z such that T = {[z'.sub.1], ..., [z'.sub.[absolute value of T]]}. Suppose T is good with respect to z, let p = [absolute value of T] and let q = n - p. Let [z.sub.min] be minimal, in the weak order on [S.sub.n], among permutations equivalent to z and whose first p entries are the elements of T. Let [z.sub.max] be maximal, in the weak order, among such permutations. Define [I.sub.T] to be the sum over the elements in the interval [st([z.sub.min][|.sub.T]), [n.sub.[down arrow]], st([z.sub.max][|.sub.T])] in [Av.sub.p] and define [J.sub.T] to be the sum over the elements in the interval [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [Av.sub.q].

Theorem 1.3. Let z [member of] [Av.sub.n]. Then

[[DELTA].sub.Av](z) = [summation over (T is good)] [I.sub.T] [cross product] [J.sub.T]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To prove Theorem 1.3, we first need several lemmas.

Lemma 1.4. The elements in the interval [[z.sub.min], [z.sub.max]] are equivalent to z and their first p entries are the elements of T.

Lemma 1.5. Suppose T [subset or equal to] [n] with [absolute value of T] = p. Let q = n - p. Suppose also that [x.sub.1] [less than or equal to] [x.sub.2] [less than or equal to] [x.sub.3] in [Av.sub.p], and that [y.sub.1] [less than or equal to] [y.sub.2] [less than or equal to] [y.sub.3] in [Av.sub.q]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 1.6. Suppose [x.sub.1], [x.sub.2] [member of] [S.sub.p] and [y.sub.1], [y.sub.2] [right arrow] [S.sub.q]. Suppose T [subset or equal to] [n], where n = p + q, and with [absolute value of T] = p. The following identities hold:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The proof of Theorem 1.3 begins by defining terms (z, T) to be the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and showing that terms(z, T) is nonempty if and only if T is good with respect to z. Next, we show that for each good subset T, the set terms(z, T) is of the form [I.sub.T] [cross product] JT. This proof also establishes the following more detailed statement.

Proposition 1.7. For some T [subset or equal to] [n], x [cross pout] y [member of] terms(z, T) if and only if x [R] y is a term of [I.sub.T] [cross product] [J.sub.T] in [[DELTA].sub.av](z).

Proof: Since x [cross product] y [member of] terms(z, T) means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we see from Equation(10) and Theorem 1.3 that for a fixed set T, x [cross product] y is a term of the summand indexed by T in [[DELTA].sub.Av](z) if and only if z is the summand indexed by T in [[DELTA].sup.*.sub.Av](x [cross product] y).

2 Pell Permutations and Sashes

Given a permutation x = [x.sub.1][x.sub.2] ... [x.sub.n] [member of] [S.sub.n], for each i [member of] [n - 1, there is a nonzero integer j such that [x.sub.i] = [x.sub.i+1] + j. If j > 0, then there is an descent of size j in the ith position of x. A Pell permutation is a permutation of [n] with no descents of size larger than 2, and such that for each descent [x.sub.i] = [x.sub.i+1] + 2, the element [x.sub.i+1] + 1 is to the right of [x.sub.i+1]. We write [P.sub.n] for the set of Pell permutations in [S.sub.n].

Let us consider how many Pell permutations of length n there are. Given x [member of] [P.sub.n-1], we can place n at the end of x or before n - 1. We can also place n before n - 2, but only if n - 1 is the last entry of x. Therefore [absolute value of [P.sub.n]] = 2[absolute value of [P.sub.n-1]] + [absolute value of [P.sub.n-2]]. This recursion, with the initial conditions [absolute value of [P.sub.0]] = 0 and [absolute value of [P.sub.1]] = 1, defines the Pell numbers as defined by [6, Sequence A000129].

Lemma 2.1. [P.sub.n] = [Av.sub.n] for U = (2(31), (41)23}.

Proof: Suppose x [member of] [P.sub.n]. Since x does not have any descents larger than 2, it avoids (41)23. For each descent [x.sub.i] = [x.sub.i+1] + 2 in x, the element [x.sub.i+1] + 1 is to the right of [x.sub.i+1]. Thus x also avoids 2(31). Now suppose x [member of] [Av.sub.n]. Suppose x has a descent [x.sub.i] = [x.sub.i+1] + j. Because x avoids 2(31), the entries [x.sub.i+1] + 1, ..., [x.sub.i+1] + j - 1 are to the right of the [x.sub.i+1]. Thus, since x avoids (41) 23 we see that j [less than or equal to] 2 and conclude that x [member of] [P.sub.n].

The poset induced on [P.sub.n] by the weak order is a lattice (also denoted by [P.sub.n]). As a consequence of Lemma 2.1, there is a Hopf algebra (K[[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]) of Pell permutations. For the rest of this paper we fix U 2(31), (41)23}.

There is a combinatorial object in bijection with Pell permutations that will allow us to have a more natural understanding of the Hopf algebra of Pell permutations.

A sash of length n is a tiling of a 1 x n rectangle by black 1 x 1 squares, white 1 x 1 squares, and/or white 1 x 2 rectangles. The set of sashes of length n is called [[SIGMA].sub.n]. There are no sashes of length -1 so [[SIGMA].sub.-1] = [empty set], and there is one sash of length 0, a 1 by 0 rectangle denoted [parallel], so [absolute value of [E.sub.0]] = 1. There are two sashes of length 1: [??] and [??]. The five sashes of length 2 and the twelve sashes of length 3 are shown in Figure 1. The poset structure of these sashes will be explained later in this section.

A sash of length n starts with either a black square, a white square, or a rectangle. Thus [absolute value of [[SIGMA].sub.n]] = 2[absolute value of [[SIGMA].sub.n-1]] + [absolute value of [[SIGMA].sub.n-2]]. Since [absolute value of [[SIGMA].sub.- 1]] = 0 and [absolute value of [[SIGMA].sub.-1]] = 1, there is a bijection between Pell permutations of length n and sashes of length n - 1. We now describe a bijection that we use to induce a Hopf Algebra structure on sashes.

Definition 2.2. We define a map a from [S.sub.n] to [[SIGMA].sub.n-1]. Let x [member of] [S.sub.n]. We build a sash [sigma](x) from left to right as we consider the entries in x from 1 to n - 1. For each value i [member of] [n - 1], if i + 1 is to the right of i, place a black square on the sash, and if i + 1 is to the left of i, place a white square on the sash. There is one exception: If i + 1 is to the right of i, and i + 2 is to the left of i (and of i + 1), then place a rectangle in the ith and [(i + 1).sup.st] positions of the sash. We also define [sigma](1) = [parallel] and [sigma]([empty set]) = [empty set].

From the definition of the map [sigma] we see that [sigma] sometimes involves replacing an adjacent black square and white square by a rectangle. Later, we will sometimes break a rectangle into a black square and a white square.

Example 2.3. Here is the procedure for computing [sigma](421365).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let T be a set of n integers and let x be a permutation of T. We define [sigma](x) = [sigma](st(x)).

Example 2.4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Definition 2.5. We define a map [eta]: [[SIGMA].sub.n-1] [right arrow] [P.sub.n]. To calculate [eta](A) for a sash A [member of] [[SIGMA].sub.n-1], we place the numbers 1 through n one at a time. Place the number 1 to begin and let i run from 1 to n - 1. If A has either a black square or the left half of a rectangle in the ith position, place i + 1 at the right end of the permutation. If A has either a white square or the right half of a rectangle in the ith position, place i + 1

immediately to the left of i or i - 1 respectively. We also define [eta]([parallel]) = 1 and [eta]([empty set]) = [empty set].

It is immediate that this construction yields a Pell permutation because the output has no descents of size larger than 2, and for each descent of size 2, the value in between the values of the descent is to the right of the descent.

Example 2.6. Here are the steps to calculate [eta](A) for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 2.7. The restriction of [sigma] to the Pell permutations is a bijection [sigma]: [P.sub.n] [right arrow] [[SIGMA].sub.n-1] whose inverse is given by [eta]: [[SIGMA].sub.n-1] [right arrow] Pn.

Theorem 2.7 is proven by showing that [sigma]([eta](A)) = A and using the fact [absolute value of [P.sub.n]] = [absolute value of [[SIGMA].sub.n-1]].

Proposition 2.8. x, y [member of] [S.sub.n] are equivalent if and only if [sigma](x) = [sigma](y).

We prove the forward direction of Proposition 2.8 by considering the case where y is obtained from x by a single [[pi].sub.[down arrow]]-move. The reverse direction is shown by contradiction.

The partial order on [[SIGMA].sub.n-1] is such that the map [sigma]: [P.sub.n] [right arrow] [[SIGMA].sub.n-1] is an order isomorphism from the lattice of Pell permutations to [[SIGMA].sub.n-1]. We refer to this lattice as [[SIGMA].sub.n-1].

From Proposition 1.2, the cover relations in [[SIGMA].sub.n-1] are exactly the relations [sigma](y) [??] [sigma](x) where x [member of] [P.sub.n] and y is covered by x in [S.sub.n].

Proposition 2.9. The cover relations on sashes are

1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any sash A and for a sash B whose leftmost tile is not a white square

2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any sash A and any sash B

3. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any sash A and any sash B

Example 2.10. See Figure 1 for the poset on [[SIGMA].sub.3] and [[SIGMA].sub.4].

3 The Hopf Algebra (and Dual Hopf Algebra) of Sashes

The bijection [sigma] allows us to carry the Hopf algebra structure on Pell permutations to a Hopf algebra structure (K[[[SIGMA].sub.[infinity]]], [*.sub.S], [[DELTA].sub.S]) on sashes and a dual Hopf algebra (K [[E.sub.[infinity]]], [[DELTA].sup.*.sub.S], [m.sup.*.sub.S]) on sashes, where K [[[SIGMA].sub.[infinity]]] is a vector space, over a field K, whose basis elements are indexed by sashes. In order to do this, we extend [sigma] and [eta] to linear maps. For each grade n of the vector space, the basis elements are represented by the sashes of length n - 1. Recall that the sash of length -1 is represented by [empty set], and the sash of length 0 is represented by [parallel]. Let A, B, and C be sashes. Using [sigma], we define a product, coproduct, dual product, and dual coproduct of sashes:

[m.sub.S](A,B) = A [*.sub.S]B = [sigma]([eta](A) [*.sub.Av] [eta](B)) (11)

[[DELTA].sub.S] (C) = ([sigma] [cross product] [sigma]) ([[DELTA].sub.av]([eta](C) (12)

[[DELTA].sup.*.sub.S](A [cross product] B) = [sigma]([[DELTA].sup.*.sub.Av]([eta]([DELTA]) [cross product] [eta](B))) (13)

[m.sup.*.sub.S](C) = ([sigma] [cross product] [sigma])([m.sup.*.sub.Av]([eta](C))) (14)

These operation definitions are somewhat unsatisfying because they require computing the operation in MR. That is, calculating a product or coproduct in this way requires mapping sashes to permutations, performing the operations in MR, throwing out the non-avoiders in the result, and then mapping the remaining permutations back to sashes. In the rest of this chapter we show how to compute these operations directly in terms of sashes.

3.1 Product

Proposition 3.1. The empty sash [empty set] is the identity for the product [[??].sub.s]. For sashes A [not equal to] [empty set] and B [not equal to] [empty set], the product A [[??].sub.s] B equals:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [SIGMA][D, E] is the sum of all the sashes in the interval [D, E] on the lattice of sashes.

The case where A = [parallel] is an instance of A [not equal to] A'[??] and similarly for B = [parallel]. In informal terms, the product of two sashes is the sum of the sashes created by joining the two sashes with a black square and a white square, and if by so doing an adjacent black square to the left of a white square is created, then the product has additional terms with rectangles in the places of the adjacent black square and white square.

The proof is obtained by applying the map [sigma] to the product of Pell permutations which is the sum over the interval [x x y', [[pi].sub.[down arrow]] (y' x x)] in the lattice of Pell permutations, where x [member of] [P.sub.p], y [member of] [P.sub.q], and y' = [(y).sub.[p+1,n]].

Example 3.2. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Notice that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.2 Dual Coproduct

From Equation (8) and Equation (4), it follows that:

[m.sup.*.sub.S](C) = [n.summation over (i=1)] [sigma]([eta](C) [|.sub.[i]]) [cross product] [sigma]([eta](C)[|.sub.[i+1,n]]) (15)

Proposition 3.3. The dual coproduct on a sash C [member of] [[SIGMA].sub.n] is given by:

[m.sup.*.sub.S](C) = [n.summation over (i=-1)] [C.sub.i] [cross product] [C.sup.n-i-1]

Where [C.sub.i] [member of] [[SIGMA].sub.i]0 is a sash identical to the first i positions of C (unless C has [??] in position i, in which case [C.sub.i] ends with [??]), and [C.sup.n-i-1] [member of] [[SIGMA].sub.n-i-1] is a sash identical to the last n - i - 1 positions of C (unless C has [??] in position i + 2, in which case [C.sup.n-i-1] begins with [??]), and we define [C.sub.0] = [C.sup.0] = [parallel] and [C.sub.-1] = [C.sup.-1] = [empty set].

The proof is given by showing that C is a term of A [[??].sub.s] B if and only if A [cross product] B is a term of [m.sup.*.sub.S](C).

3.3 Dual Product

From Equation (9), it follows that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

We now prepare to describe the dual product [[DELTA].sup.*.sub.S] directly on sashes.

Definition 3.4. Given a set T [subset or equal to] [n] such that [absolute value of T] = p and n = p + q, and given sashes D [member of] [[SIGMA].sub.p-1] and E [member of] [[SIGMA].sub.q-1], define a sash [gamma]T(D [cross product] E by the following steps. First, write D above E. Then, label D with T, by placing the elements of T in increasing order between each position of D, including the beginning and end. Label E similarly using the elements of [T.sup.C].

Example 3.5. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next, draw arrows from i to i + 1 for all i [member of] [n - 1]. Lastly, follow the path of the arrows placing elements in a new sash based on the following criteria:

Place a rectangle in the ith and [(i + 1).sup.st] positions of the new sash if either of the following conditions are met:

1. if the ith arrow is from D to E, the [(i + 1).sup.st] arrow is from E to D, and there is a [??] or [??] in D in between i and i + 2

2. if the arrow is from E to E, the [(i + 1).sup.st] arrow is from E to D, and there is a [??] or [??] in E in between i and i + 1

If the above criteria are not met, then the following rules apply:

1. if the ith arrow is from D to D (or from E to E), place whatever is in between i and i + 1 in D (or in E) in the ith position.

2. if the ith arrow is from D to E, place a black square in the ith position.

3. if the ith arrow is from E to D, place a white square in the ith position.

Note that it may be necessary to replace the left half of a rectangle by a black square or to replace the right half of a rectangle by a white square (as in the first step of the example below).

Example 3.6. Let T, D, and E be as in Example 3.5. Then we compute [[gamma].sub.T](D [cross product] E) to obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 3.7. The dual product of sashes D [member of] [[SIGMA].sub.p-1] and E [member of] [[SIGMA].sub.q-1], for p + q = n, is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.4 Coproduct

We now describe the coproduct in the Hopf algebra of sashes and we begin with some definitions.

Definition 3.8. For C [sigma] [[SIGMA].sub.n-1], a dotting of C is C with a dot in any subset of the n - 1 positions of C. An allowable dotting of C is a dotting of C that meets all of the following conditions

1. has at least one dot

2. the first dot can be in any position, and dotted positions alternate between a black square (or the left half of a rectangle) and a white square (or the right half of a rectangle)

3. has no instances of [??]

Figure 2 shows the allowable dottings of the sash [??].

Consider an allowable dotting d = [c.sub.1] [*.sub.1] [c.sub.2] [*.sub.2] ... [c.sub.j][*.sub.j][c.sub.j+1] of a sash C, where each [c.sub.i] is a sub sash of C without any dots, and [*.sub.i] is a single dotted position. If any [*.sub.i] is on the right half of a rectangle, then the the left half of the rectangle in the last position of [c.sub.i] is replaced by a black square. If [*.sub.i] and [*.sub.i+1] are in adjacent positions, then [c.sub.i+1] = [parallel]. (If any [*.sub.i] is on the left half of a rectangle, then [*.sub.i+1] is on the right half of the same rectangle, so [c.sub.i+1] = [parallel].)

We use C and d to define two objects A and B that are similar to sashes, but have an additional type of square [??] which we call a mystery square. If [*.sub.1] is on a black square or the left half of a rectangle, then let A be the concatenation of the odd [c.sub.i] with a mystery square in between each [c.sub.i] (where i is odd), and let B be the concatenation of the even [c.sub.i] with a mystery square in between each [c.sub.i] (where i is even). For example, if [*.sub.i] is on a black square and j is even, then A = [c.sub.1] [??] [c.sub.3] [??] ... [??] [c.sub.j+1] and B = [c.sub.2] [??] [c.sub.4] [??] ... [??] [c.sub.j]. If [*] 1 is on a white square or the right half of a rectangle, then let A be the concatenation of the even [right arrow[].sub.i] with a mystery square in between each [c.sub.i], and let B be the concatenation of the odd [c.sub.i] with a mystery square in between each [c.sub.i].

We use the objects A and B to define four sashes [A.bar], [bar.A], [B.bar], and [bar.B].

To compute [A.bar], consider each mystery square in A. If the mystery square follows [c.sub.i] and the ith and [(i + 1).sup.st] dots of d are on the same rectangle, [??], then replace the mystery square after [c.sub.i] with a white square. Otherwise replace the mystery square with a black square.

To compute [bar.A], consider each mystery square in A from left to right. If the mystery square follows [c.sub.i] and the ith and [(i + 1).sup.st] dots of d are on an adjacent black square and white square, [??], then we check to see whether or not the mystery square is followed by a white square. If the mystery square is followed by a white square (i.e. if [c.sub.i+2] starts with a white square), then replace the mystery square and the white square with a rectangle. Otherwise replace the mystery square with a black square. If the mystery square follows [c.sub.i] and the ith and [(i + 1).sup.st] dots of d are not on an adjacent black square and white square, then we check to see whether or not the mystery square is preceded by a black square. If either [c.sub.i] ends in a black square or [c.sub.i] = [parallel] and the previous mystery square has been changed to a black square, then replace the mystery square after [c.sub.i] and the black square before it with a rectangle. Otherwise replace the mystery square after [c.sub.i] with a white square.

To compute [B.bar], replace all mystery squares of B with black squares.

To compute [bar.B], replace all mystery squares of B with white squares, unless the mystery square is preceded by a black square, in which case replace both the black square and the mystery square with a rectangle.

Example 3.9. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is on a black square. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using the rules above to compute A, B, and the four sashes [A.bar], [bar.A], [B.bar], and [bar.B], we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Given an allowable dotting d of a sash C we define [I.sub.d] = [A.bar], [bar.A]] and [J.sub.d] = [SIGMA][[B.bar], [bar.B]] for [A.bar], [bar.A], [B.bar], and [bar.B] computed as above. Thus the notation [I.sub.d] [cross product] [J.sub.d] denotes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 3.10. Given C [member of] [[SIGMA].sub.n-1]:

[[SIGMA].sub.s](C) = [empty set] [cross product] C + C [cross product] [empty set] + [summation over (allowable dottings d of C)] [I.sub.d] [cross product] [J.sub.d]

References

[1] Marcelo Aguiar, Nantel Bergeron, and Frank Sottile. Combinatorial Hopf algebras and generalized Dehn-Sommerville relations. Compos. Math., 142(1):1-30, 2006.

[2] Eric Babson and Einar Steingrimsson. Generalized permutation patterns and a classification of the Mahonian statistics. Sem. Lothar. Combin., 44:Art. B44b, 18 pp. (electronic), 2000.

[3] Jean-Louis Loday and Maria O. Ronco. Hopf algebra of the planar binary trees. Adv. Math., 139(2):293-309, 1998.

[4] Claudia Malvenuto. Produits et coproduits des fonctions quasi-symetriques et de l'algebre des descentes. (LACIM), 16, 1994.

[5] Nathan Reading. Lattice congruences, fans and Hopf algebras. J. Combin. Theory Ser. A, 110(2):237-273, 2005.

[6] N. J. A. Sloane. The on-line encyclopedia of integer sequences. http://oeis.org. 2013.

Shirley Law *

Washington College, USA

* Email: slaw2@washcoll.edu.

The focus of this research is on combinatorial Hopf algebras: Hopf algebras such that the basis elements of the underlying vector space are indexed by a family of combinatorial objects. For each n [greater than or equal to] 0, let [O.sub.n] be a finite set of "combinatorial objects". We define a graded vector space over a field K, such that for each grade n the basis vectors of the vector space are indexed by the elements of [O.sub.n]. That is, the graded vector space is: K[[O.sub.[infinity]]] = [[direct sum].sub.n[greater than or equal to]0] K[[O.sub.n]]. For simplicity, we refer to a basis element of this vector space by the combinatorial object indexing it. There is a more sophisticated approach for defining combinatorial Hopf algebras. For more information see [1].

Let [S.sub.n] be the group of permutations of the set of the first n integers [n] = {1, 2,..., n}. Also define [n, n'] = {n, n + 1, ..., n'} for n' [greater than or equal to] n. For x = [x.sub.1][x.sub.2] ... [x.sub.n] [member of] [S.sub.n], an inversion of x is a pair ([x.sub.i], [x.sub.j]) where i < j and [x.sub.i] > [x.sub.j], and the inversion set of x is the set of all such inversions. The weak order is the partial order on [S.sub.n] with x [less than or equal to] x' if and only if the inversion set of x is contained in the inversion set of x'. The weak order is a lattice. The inverse [x.sup.-1] of a permutation x [member of] [S.sub.n] is the permutation [x.sup.~1] = y = [y.sub.1] ... [y.sub.n] [member of] Sn [s.sub.uch] that [y.sub.i] = j when [x.sub.j] = i.

Let T be a set consisting of integers [t.sub.1] < [t.sub.2] < ... < [t.sub.n]. Given a permutation x [member of] [S.sub.n], the notation [(x).sub.T] stands for the permutation of T whose one-line notation has [t.sub.j] in the [i.sup.th] position when [x.sub.i] = j. On the other hand, given a permutation x of T, the standardization, st(x), is the unique permutation y [member of] [S.sub.n] such that [(y).sub.T] = x.

Now let T be a subset of [n]. For x [member of] [S.sup.n], the permutation x[|.sub.T] is the permutation of T obtained by removing from the one-line notation for x all entries that are not elements of T.

Example 1.1. Let x = 31254, [T.sub.1] = {2,3,6, 8, 9}, and [T.sub.2] = {2, 3, 5}. Then, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and thus st(62398) = 31254. Also, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The Malvenuto-Reutenauer Hopf algebra MR is a graded Hopf Algebra (K[[S.sub.[infinity]]], *, [delta]). Let K[[S.sub.[infinity]]] = [[direct sum].sub.n[greater than or equal to]0] K[[S.sub.n]] be a graded vector space. Let x = [x.sub.1][x.sub.2] ... [x.sub.1][x.sub.2] [x.sub.p] [member of] [S.sub.p] and y = [y.sub.1][y.sub.2] ... [y.sub.q] [member of] [S.sub.q]. Define y' = [y'.sub.1] ... [y'.sub.q] to be [(y).sub.[p+1,p+q]] so that [y'.sub.i] = [y.sub.i] + p. A shifted shuffle of x and y' is a permutation z [member of] [S.sub.n] where n = p + q, z[|.sub.[p]] = x and Z [|.sub.[p+1,n]] = y'. From [3], the product of x and y in MR is the sum of all the shifted shuffles of x and y. Equivalently,

x x y = [SIGMA][x x y', y' x x] (1)

where x x y' is the concatenation of the permutations x and y', and [SIGMA][x x y', y' x x] denotes the sum of all the elements in the weak order interval [x x y', y' x x]. The poset induced on [S.sub.n] by the weak order is a lattice (also denoted by [S.sub.n]). The coproduct in MR is:

[DELTA](x) = [p.summation over (i=0)] st([x.sub.1] ... [x.sub.i]) [cross product] st([x.sub.i+1] ... [x.sub.p]) (2)

where st([x.sub.1] ... [x.sub.0]) and st([x.sub.p+1] ... [x.sub.p]) are both interpreted as the empty permutation [empty set].

Define the map Inv: [S.sub.n] [right arrow] [S.sub.n] by Inv(x) = [x.sup.-1] and extend the map linearly to a map Inv: K[S.sub.[infinity]] [right arrow] K[S.sub.[infinity]]. MR is known to be self dual [4] and specifically Inv is an isomorphism from (K[[S.sub.[infinity]]], *, [DELTA]) to the graded dual Hopf algebra (K [[S.sub.[infinity]]], [[DELTA].sup.*], [m.sup.*]). Let x [member of] [S.sub.q], y [member of] [S.sub.q], and z e [S.sub.n], where p + q = n. Given a subset T of p elements of [n], TC denotes the complement of T in [n]. The dual product is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3)

and the dual coproduct is:

[m.sup.*](z) = (Inv [cross product] Inv)([DELTA]([z.sup.-1]) = [n.summation over (i=0)] z[|.sub.[i]] [cross product] st(z[|.sub.[i+1,n]]) (4)

where z[|.sub.[0]] and z[|.sub.[n+i,n]] are both interpreted as the empty permutation [empty set].

Now that we have explicitly described both the Hopf algebra of permutations and the dual Hopf algebra of permutations, we will present a family of Hopf subalgebras that are defined by a particular patternavoidance condition. We give more detail on the particular pattern-avoidance condition below, but in general the condition requires patterns of length k to have k and 1 adjacent. This family of Hopf algebras is defined by Reading [5].

For some k [greater than or equal to] 2, let V [subset or equal to] [2, k - 1] such that [absolute value of V] = j and let [V.sup.C] be the complement of V in [2, k - 1]. A permutation x [member of] [S.sub.n] avoids the pattern V(k1) [V.sup.C] if for every subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of x with [j.sub.+2] = [i.sub.j+1] + 1, the standardization [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is not of the form [upsilon](k1)[upsilon]' for any permutation v of the set V and any permutation [upsilon]' of [V.sup.C]. In the notation of Babson and Steingrimsson [2] avoiding V (k1) [V.sup.C] means avoiding all patterns of the form [[upsilon].sub.1] - ... - [[upsilon].sub.j] - k1 - [[upsilon]'.sub.1] - ... - [[upsilon]'.sub.k-j-2], where [[upsilon].sub.1] ... [[upsilon].sub.j] is a permutation of V and [[upsilon]'.sub.1] .. [[upsilon]'.sub.k-j-2] is a permutation of [V.sup.C].

Let U be a set of patterns of the form V(k1)[V.sup.C], where [absolute value of V] and k can vary. Define [Av.sub.n] to be the set of permutations in [S.sub.n] that avoid all of the patterns in U. We define a graded Hopf algebra (K[[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]) as a graded Hopf subalgebra of MR. Let K[[Av.sub.n]] be a vector space, over a field K, with basis vectors indexed by the elements of [Av.sub.n], and let K[[Av.sub.[infinity]]] be the graded vector space [direct sum].sub.n[greater than or equal to]0] K[[Av.sub.n]]. The product and coproduct on K[[Av.sub.[infinity]]] are described below.

We define a map [[pi].sub.[down arrow]]: [S.sub.n] [right arrow] [Av.sub.n] recursively. If x [member of] [Av.sub.n] then define [[pi].sub.[down arrow]](x) = x. If x [member of] [S.sub.n], but x [not member of] [Av.sub.n], then x contains an instance of a pattern V(k1) [V.sup.C] in U. That is, there exists some subsequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of x, where [i.sub.j+2] = [i.sub.j+1] + 1 and j = [absolute value of V], such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some permutations [upsilon] and [upsilon]' of V and [V.sup.C]. Exchange [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in x to create a new permutation x', calculate [n.sub.[down arrow]](x') recursively and set [n.sub.[down arrow]] (x) = [n.sub.[down arrow]] (x'). The recursion must terminate because an inversion of x is destroyed at every step, and because the identity permutation is in [Av.sub.n]. The map [n.sub.[down arrow]], is well-defined as explained in [5, Remark 9.5]. We emphasize that the definition of [n.sub.[down arrow]], is dependent on U.

The map [n.sub.[down arrow]] defines an equivalence relation with permutations x, x' [member of] [S.sub.n] equivalent if and only if [n.sub.[down arrow]] (x) = [n.sub.[down arrow]] (x'). The set [Av.sub.n] is a set of representatives of these equivalence classes. This equivalence relation is a lattice congruence on the weak order. Therefore the poset induced on [Av.sub.n] by the weak order is a lattice (also denoted by [Av.sub.n]) and the map [n.sub.[down arrow]] is a lattice homomorphism from the weak order to [Av.sub.n]. The congruence classes defined by [n.sub.[down arrow]] are intervals, and [n.sub.[down arrow]] maps an element to the minimal element of its congruence class. Let [n.sub.[up arrow]] be the map that takes an element to the maximal element of its congruence class.

The following proposition is a special case of [5, Proposition 2.2]. The congruence on [S.sub.n] defined by [n.sub.[down arrow]], is denoted by [THETA]. For x [member of] [S.sub.n], the congruence class of x mod [THETA] is denoted by [[x].sub.[THETA]].

Proposition 1.2. Given [S.sub.n] a finite lattice, [THETA] a congruence on [S.sub.n], and x [member of] [S.sub.n], the map y [right arrow] [[y].sub.[THETA]] restricts to a one-to-one correspondence between elements of [S.sub.n] covered by [n.sub.[down arrow]] (x) and elements of [Av.sub.n] covered by [[x].sub.[THETA]].

Both [n.sub.[down arrow]], and [n.sub.[up arrow]] are order preserving and [n.sub.[up arrow]] x [n.sub.[down arrow]] = [n.sub.[up arrow]] and [n.sub.[down arrow]] x [n.sub.[up arrow]] = [n.sub.[down arrow]]. A [n.sub.[down arrow]]-move is the result of switching two adjacent entries of a permutation in the manner described above. That is, it changes ... k1 ... to ... 1k ... for some pattern in U. A [n.sub.[up arrow]]-move is the result of switching two adjacent entries of a permutation in a way such that a [n.sub.[up arrow]]-move undoes a [n.sub.[down arrow]]-move. That is, it changes ... 1k ... to ... k1 ....

We define a map r: K[[S.sub.[infinity]]] [right arrow] K[[Av.sub.[infinity]]] that identifies the representative of a congruence class. Given

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Similarly, we define a map c: K[[Av.sub.[infinity]]] [right arrow] K[[S.sub.[infinity]]] that takes an avoider to the sum of its congruence class:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now describe the product and coproduct in (K [[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]). Let x [member of] [Av.sub.p], and let y [member of] [Av.sub.q]. Then:

[m.sub.Av](x [cross product] y) = x[*.sub.Av] y = r(x x y). (5)

Just as the product in MR is [SIGMA][x x y', y' x x|, we can view this product as:

x [*.sub.Av] y = [SIGMA][x x y', [n.sub.[down arrow]](y' x x)], (6)

where [x x y', [n.sub.[down arrow]] (y' x x)] is an interval on the lattice [Av.sub.n].

The coproduct is:

[[DELTA].sub.av](z) = (r [cross product] r) ([DELTA](c(z))). (7)

We now describe the Hopf algebra (K[[Av.sub.[infinity]]], [[DELTA].sup.*.sub.Av], [*.sup.*.sub.Av]) that is dual to (K[[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]). We extend the map [n.sub.[down arrow]] linearly, so [n.sub.[down arrow]] is a map from K[[S.sub.[infinity]]] to K[[Av.sub.[infinity]]]. The map that is dual to the map c is [c.sup.*]: K[[S.sub.[infinity]]] [right arrow] K[[Av.sub.[infinity]]], where [c.sup.*](x) = [n.sub.[down arrow]] (x) for x [member of] K[[S.sub.[infinity]]]. The map that is dual to the map r is [r.sup.*]: K[[Av.sub.[infinity]]] [right arrow] K[[S.sub.[infinity]]], where [r.sup.*](x) = x for x [member of] K[[Av.sub.[infinity]]].

Let z [member of] [Av.sub.n], where n = p + q. The dual coproduct is given by dualizing Equation (5), so that:

[m.sup.*.sub.Av](z) = [m.sup.*](z). (8)

The dual product [[DELTA].sup.*.sub.Av] is given by dualizing Equation (7):

[[DELTA].sup.*.sub.Av](x [cross product] y) = [n.sub.[down arrow]] [[DELTA].sup.*](x [cross product] y). (9)

Combining Equation (9) with Equation (3), we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

Equation (10) leads to the following order theoretic description of the coproduct [[DELTA].sub.Av], which was worked out jointly with Nathan Reading.

Given z [member of] [Av.sub.n], a subset T [subset or equal to] [n] is good with respect to z if there exists a permutation z' = [z'.sub.1] ... [z'.sub.n] with [n.sub.[down arrow]](z') = z such that T = {[z'.sub.1], ..., [z'.sub.[absolute value of T]]}. Suppose T is good with respect to z, let p = [absolute value of T] and let q = n - p. Let [z.sub.min] be minimal, in the weak order on [S.sub.n], among permutations equivalent to z and whose first p entries are the elements of T. Let [z.sub.max] be maximal, in the weak order, among such permutations. Define [I.sub.T] to be the sum over the elements in the interval [st([z.sub.min][|.sub.T]), [n.sub.[down arrow]], st([z.sub.max][|.sub.T])] in [Av.sub.p] and define [J.sub.T] to be the sum over the elements in the interval [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [Av.sub.q].

Theorem 1.3. Let z [member of] [Av.sub.n]. Then

[[DELTA].sub.Av](z) = [summation over (T is good)] [I.sub.T] [cross product] [J.sub.T]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To prove Theorem 1.3, we first need several lemmas.

Lemma 1.4. The elements in the interval [[z.sub.min], [z.sub.max]] are equivalent to z and their first p entries are the elements of T.

Lemma 1.5. Suppose T [subset or equal to] [n] with [absolute value of T] = p. Let q = n - p. Suppose also that [x.sub.1] [less than or equal to] [x.sub.2] [less than or equal to] [x.sub.3] in [Av.sub.p], and that [y.sub.1] [less than or equal to] [y.sub.2] [less than or equal to] [y.sub.3] in [Av.sub.q]. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 1.6. Suppose [x.sub.1], [x.sub.2] [member of] [S.sub.p] and [y.sub.1], [y.sub.2] [right arrow] [S.sub.q]. Suppose T [subset or equal to] [n], where n = p + q, and with [absolute value of T] = p. The following identities hold:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The proof of Theorem 1.3 begins by defining terms (z, T) to be the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and showing that terms(z, T) is nonempty if and only if T is good with respect to z. Next, we show that for each good subset T, the set terms(z, T) is of the form [I.sub.T] [cross product] JT. This proof also establishes the following more detailed statement.

Proposition 1.7. For some T [subset or equal to] [n], x [cross pout] y [member of] terms(z, T) if and only if x [R] y is a term of [I.sub.T] [cross product] [J.sub.T] in [[DELTA].sub.av](z).

Proof: Since x [cross product] y [member of] terms(z, T) means that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we see from Equation(10) and Theorem 1.3 that for a fixed set T, x [cross product] y is a term of the summand indexed by T in [[DELTA].sub.Av](z) if and only if z is the summand indexed by T in [[DELTA].sup.*.sub.Av](x [cross product] y).

2 Pell Permutations and Sashes

Given a permutation x = [x.sub.1][x.sub.2] ... [x.sub.n] [member of] [S.sub.n], for each i [member of] [n - 1, there is a nonzero integer j such that [x.sub.i] = [x.sub.i+1] + j. If j > 0, then there is an descent of size j in the ith position of x. A Pell permutation is a permutation of [n] with no descents of size larger than 2, and such that for each descent [x.sub.i] = [x.sub.i+1] + 2, the element [x.sub.i+1] + 1 is to the right of [x.sub.i+1]. We write [P.sub.n] for the set of Pell permutations in [S.sub.n].

Let us consider how many Pell permutations of length n there are. Given x [member of] [P.sub.n-1], we can place n at the end of x or before n - 1. We can also place n before n - 2, but only if n - 1 is the last entry of x. Therefore [absolute value of [P.sub.n]] = 2[absolute value of [P.sub.n-1]] + [absolute value of [P.sub.n-2]]. This recursion, with the initial conditions [absolute value of [P.sub.0]] = 0 and [absolute value of [P.sub.1]] = 1, defines the Pell numbers as defined by [6, Sequence A000129].

Lemma 2.1. [P.sub.n] = [Av.sub.n] for U = (2(31), (41)23}.

Proof: Suppose x [member of] [P.sub.n]. Since x does not have any descents larger than 2, it avoids (41)23. For each descent [x.sub.i] = [x.sub.i+1] + 2 in x, the element [x.sub.i+1] + 1 is to the right of [x.sub.i+1]. Thus x also avoids 2(31). Now suppose x [member of] [Av.sub.n]. Suppose x has a descent [x.sub.i] = [x.sub.i+1] + j. Because x avoids 2(31), the entries [x.sub.i+1] + 1, ..., [x.sub.i+1] + j - 1 are to the right of the [x.sub.i+1]. Thus, since x avoids (41) 23 we see that j [less than or equal to] 2 and conclude that x [member of] [P.sub.n].

The poset induced on [P.sub.n] by the weak order is a lattice (also denoted by [P.sub.n]). As a consequence of Lemma 2.1, there is a Hopf algebra (K[[Av.sub.[infinity]]], [*.sub.Av], [[DELTA].sub.Av]) of Pell permutations. For the rest of this paper we fix U 2(31), (41)23}.

There is a combinatorial object in bijection with Pell permutations that will allow us to have a more natural understanding of the Hopf algebra of Pell permutations.

A sash of length n is a tiling of a 1 x n rectangle by black 1 x 1 squares, white 1 x 1 squares, and/or white 1 x 2 rectangles. The set of sashes of length n is called [[SIGMA].sub.n]. There are no sashes of length -1 so [[SIGMA].sub.-1] = [empty set], and there is one sash of length 0, a 1 by 0 rectangle denoted [parallel], so [absolute value of [E.sub.0]] = 1. There are two sashes of length 1: [??] and [??]. The five sashes of length 2 and the twelve sashes of length 3 are shown in Figure 1. The poset structure of these sashes will be explained later in this section.

A sash of length n starts with either a black square, a white square, or a rectangle. Thus [absolute value of [[SIGMA].sub.n]] = 2[absolute value of [[SIGMA].sub.n-1]] + [absolute value of [[SIGMA].sub.n-2]]. Since [absolute value of [[SIGMA].sub.- 1]] = 0 and [absolute value of [[SIGMA].sub.-1]] = 1, there is a bijection between Pell permutations of length n and sashes of length n - 1. We now describe a bijection that we use to induce a Hopf Algebra structure on sashes.

Definition 2.2. We define a map a from [S.sub.n] to [[SIGMA].sub.n-1]. Let x [member of] [S.sub.n]. We build a sash [sigma](x) from left to right as we consider the entries in x from 1 to n - 1. For each value i [member of] [n - 1], if i + 1 is to the right of i, place a black square on the sash, and if i + 1 is to the left of i, place a white square on the sash. There is one exception: If i + 1 is to the right of i, and i + 2 is to the left of i (and of i + 1), then place a rectangle in the ith and [(i + 1).sup.st] positions of the sash. We also define [sigma](1) = [parallel] and [sigma]([empty set]) = [empty set].

From the definition of the map [sigma] we see that [sigma] sometimes involves replacing an adjacent black square and white square by a rectangle. Later, we will sometimes break a rectangle into a black square and a white square.

Example 2.3. Here is the procedure for computing [sigma](421365).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let T be a set of n integers and let x be a permutation of T. We define [sigma](x) = [sigma](st(x)).

Example 2.4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Definition 2.5. We define a map [eta]: [[SIGMA].sub.n-1] [right arrow] [P.sub.n]. To calculate [eta](A) for a sash A [member of] [[SIGMA].sub.n-1], we place the numbers 1 through n one at a time. Place the number 1 to begin and let i run from 1 to n - 1. If A has either a black square or the left half of a rectangle in the ith position, place i + 1 at the right end of the permutation. If A has either a white square or the right half of a rectangle in the ith position, place i + 1

immediately to the left of i or i - 1 respectively. We also define [eta]([parallel]) = 1 and [eta]([empty set]) = [empty set].

It is immediate that this construction yields a Pell permutation because the output has no descents of size larger than 2, and for each descent of size 2, the value in between the values of the descent is to the right of the descent.

Example 2.6. Here are the steps to calculate [eta](A) for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 2.7. The restriction of [sigma] to the Pell permutations is a bijection [sigma]: [P.sub.n] [right arrow] [[SIGMA].sub.n-1] whose inverse is given by [eta]: [[SIGMA].sub.n-1] [right arrow] Pn.

Theorem 2.7 is proven by showing that [sigma]([eta](A)) = A and using the fact [absolute value of [P.sub.n]] = [absolute value of [[SIGMA].sub.n-1]].

Proposition 2.8. x, y [member of] [S.sub.n] are equivalent if and only if [sigma](x) = [sigma](y).

We prove the forward direction of Proposition 2.8 by considering the case where y is obtained from x by a single [[pi].sub.[down arrow]]-move. The reverse direction is shown by contradiction.

The partial order on [[SIGMA].sub.n-1] is such that the map [sigma]: [P.sub.n] [right arrow] [[SIGMA].sub.n-1] is an order isomorphism from the lattice of Pell permutations to [[SIGMA].sub.n-1]. We refer to this lattice as [[SIGMA].sub.n-1].

From Proposition 1.2, the cover relations in [[SIGMA].sub.n-1] are exactly the relations [sigma](y) [??] [sigma](x) where x [member of] [P.sub.n] and y is covered by x in [S.sub.n].

Proposition 2.9. The cover relations on sashes are

1. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any sash A and for a sash B whose leftmost tile is not a white square

2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any sash A and any sash B

3. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any sash A and any sash B

Example 2.10. See Figure 1 for the poset on [[SIGMA].sub.3] and [[SIGMA].sub.4].

3 The Hopf Algebra (and Dual Hopf Algebra) of Sashes

The bijection [sigma] allows us to carry the Hopf algebra structure on Pell permutations to a Hopf algebra structure (K[[[SIGMA].sub.[infinity]]], [*.sub.S], [[DELTA].sub.S]) on sashes and a dual Hopf algebra (K [[E.sub.[infinity]]], [[DELTA].sup.*.sub.S], [m.sup.*.sub.S]) on sashes, where K [[[SIGMA].sub.[infinity]]] is a vector space, over a field K, whose basis elements are indexed by sashes. In order to do this, we extend [sigma] and [eta] to linear maps. For each grade n of the vector space, the basis elements are represented by the sashes of length n - 1. Recall that the sash of length -1 is represented by [empty set], and the sash of length 0 is represented by [parallel]. Let A, B, and C be sashes. Using [sigma], we define a product, coproduct, dual product, and dual coproduct of sashes:

[m.sub.S](A,B) = A [*.sub.S]B = [sigma]([eta](A) [*.sub.Av] [eta](B)) (11)

[[DELTA].sub.S] (C) = ([sigma] [cross product] [sigma]) ([[DELTA].sub.av]([eta](C) (12)

[[DELTA].sup.*.sub.S](A [cross product] B) = [sigma]([[DELTA].sup.*.sub.Av]([eta]([DELTA]) [cross product] [eta](B))) (13)

[m.sup.*.sub.S](C) = ([sigma] [cross product] [sigma])([m.sup.*.sub.Av]([eta](C))) (14)

These operation definitions are somewhat unsatisfying because they require computing the operation in MR. That is, calculating a product or coproduct in this way requires mapping sashes to permutations, performing the operations in MR, throwing out the non-avoiders in the result, and then mapping the remaining permutations back to sashes. In the rest of this chapter we show how to compute these operations directly in terms of sashes.

3.1 Product

Proposition 3.1. The empty sash [empty set] is the identity for the product [[??].sub.s]. For sashes A [not equal to] [empty set] and B [not equal to] [empty set], the product A [[??].sub.s] B equals:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [SIGMA][D, E] is the sum of all the sashes in the interval [D, E] on the lattice of sashes.

The case where A = [parallel] is an instance of A [not equal to] A'[??] and similarly for B = [parallel]. In informal terms, the product of two sashes is the sum of the sashes created by joining the two sashes with a black square and a white square, and if by so doing an adjacent black square to the left of a white square is created, then the product has additional terms with rectangles in the places of the adjacent black square and white square.

The proof is obtained by applying the map [sigma] to the product of Pell permutations which is the sum over the interval [x x y', [[pi].sub.[down arrow]] (y' x x)] in the lattice of Pell permutations, where x [member of] [P.sub.p], y [member of] [P.sub.q], and y' = [(y).sub.[p+1,n]].

Example 3.2. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Notice that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.2 Dual Coproduct

From Equation (8) and Equation (4), it follows that:

[m.sup.*.sub.S](C) = [n.summation over (i=1)] [sigma]([eta](C) [|.sub.[i]]) [cross product] [sigma]([eta](C)[|.sub.[i+1,n]]) (15)

Proposition 3.3. The dual coproduct on a sash C [member of] [[SIGMA].sub.n] is given by:

[m.sup.*.sub.S](C) = [n.summation over (i=-1)] [C.sub.i] [cross product] [C.sup.n-i-1]

Where [C.sub.i] [member of] [[SIGMA].sub.i]0 is a sash identical to the first i positions of C (unless C has [??] in position i, in which case [C.sub.i] ends with [??]), and [C.sup.n-i-1] [member of] [[SIGMA].sub.n-i-1] is a sash identical to the last n - i - 1 positions of C (unless C has [??] in position i + 2, in which case [C.sup.n-i-1] begins with [??]), and we define [C.sub.0] = [C.sup.0] = [parallel] and [C.sub.-1] = [C.sup.-1] = [empty set].

The proof is given by showing that C is a term of A [[??].sub.s] B if and only if A [cross product] B is a term of [m.sup.*.sub.S](C).

3.3 Dual Product

From Equation (9), it follows that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

We now prepare to describe the dual product [[DELTA].sup.*.sub.S] directly on sashes.

Definition 3.4. Given a set T [subset or equal to] [n] such that [absolute value of T] = p and n = p + q, and given sashes D [member of] [[SIGMA].sub.p-1] and E [member of] [[SIGMA].sub.q-1], define a sash [gamma]T(D [cross product] E by the following steps. First, write D above E. Then, label D with T, by placing the elements of T in increasing order between each position of D, including the beginning and end. Label E similarly using the elements of [T.sup.C].

Example 3.5. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Next, draw arrows from i to i + 1 for all i [member of] [n - 1]. Lastly, follow the path of the arrows placing elements in a new sash based on the following criteria:

Place a rectangle in the ith and [(i + 1).sup.st] positions of the new sash if either of the following conditions are met:

1. if the ith arrow is from D to E, the [(i + 1).sup.st] arrow is from E to D, and there is a [??] or [??] in D in between i and i + 2

2. if the arrow is from E to E, the [(i + 1).sup.st] arrow is from E to D, and there is a [??] or [??] in E in between i and i + 1

If the above criteria are not met, then the following rules apply:

1. if the ith arrow is from D to D (or from E to E), place whatever is in between i and i + 1 in D (or in E) in the ith position.

2. if the ith arrow is from D to E, place a black square in the ith position.

3. if the ith arrow is from E to D, place a white square in the ith position.

Note that it may be necessary to replace the left half of a rectangle by a black square or to replace the right half of a rectangle by a white square (as in the first step of the example below).

Example 3.6. Let T, D, and E be as in Example 3.5. Then we compute [[gamma].sub.T](D [cross product] E) to obtain:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 3.7. The dual product of sashes D [member of] [[SIGMA].sub.p-1] and E [member of] [[SIGMA].sub.q-1], for p + q = n, is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.4 Coproduct

We now describe the coproduct in the Hopf algebra of sashes and we begin with some definitions.

Definition 3.8. For C [sigma] [[SIGMA].sub.n-1], a dotting of C is C with a dot in any subset of the n - 1 positions of C. An allowable dotting of C is a dotting of C that meets all of the following conditions

1. has at least one dot

2. the first dot can be in any position, and dotted positions alternate between a black square (or the left half of a rectangle) and a white square (or the right half of a rectangle)

3. has no instances of [??]

Figure 2 shows the allowable dottings of the sash [??].

Consider an allowable dotting d = [c.sub.1] [*.sub.1] [c.sub.2] [*.sub.2] ... [c.sub.j][*.sub.j][c.sub.j+1] of a sash C, where each [c.sub.i] is a sub sash of C without any dots, and [*.sub.i] is a single dotted position. If any [*.sub.i] is on the right half of a rectangle, then the the left half of the rectangle in the last position of [c.sub.i] is replaced by a black square. If [*.sub.i] and [*.sub.i+1] are in adjacent positions, then [c.sub.i+1] = [parallel]. (If any [*.sub.i] is on the left half of a rectangle, then [*.sub.i+1] is on the right half of the same rectangle, so [c.sub.i+1] = [parallel].)

We use C and d to define two objects A and B that are similar to sashes, but have an additional type of square [??] which we call a mystery square. If [*.sub.1] is on a black square or the left half of a rectangle, then let A be the concatenation of the odd [c.sub.i] with a mystery square in between each [c.sub.i] (where i is odd), and let B be the concatenation of the even [c.sub.i] with a mystery square in between each [c.sub.i] (where i is even). For example, if [*.sub.i] is on a black square and j is even, then A = [c.sub.1] [??] [c.sub.3] [??] ... [??] [c.sub.j+1] and B = [c.sub.2] [??] [c.sub.4] [??] ... [??] [c.sub.j]. If [*] 1 is on a white square or the right half of a rectangle, then let A be the concatenation of the even [right arrow[].sub.i] with a mystery square in between each [c.sub.i], and let B be the concatenation of the odd [c.sub.i] with a mystery square in between each [c.sub.i].

We use the objects A and B to define four sashes [A.bar], [bar.A], [B.bar], and [bar.B].

To compute [A.bar], consider each mystery square in A. If the mystery square follows [c.sub.i] and the ith and [(i + 1).sup.st] dots of d are on the same rectangle, [??], then replace the mystery square after [c.sub.i] with a white square. Otherwise replace the mystery square with a black square.

To compute [bar.A], consider each mystery square in A from left to right. If the mystery square follows [c.sub.i] and the ith and [(i + 1).sup.st] dots of d are on an adjacent black square and white square, [??], then we check to see whether or not the mystery square is followed by a white square. If the mystery square is followed by a white square (i.e. if [c.sub.i+2] starts with a white square), then replace the mystery square and the white square with a rectangle. Otherwise replace the mystery square with a black square. If the mystery square follows [c.sub.i] and the ith and [(i + 1).sup.st] dots of d are not on an adjacent black square and white square, then we check to see whether or not the mystery square is preceded by a black square. If either [c.sub.i] ends in a black square or [c.sub.i] = [parallel] and the previous mystery square has been changed to a black square, then replace the mystery square after [c.sub.i] and the black square before it with a rectangle. Otherwise replace the mystery square after [c.sub.i] with a white square.

To compute [B.bar], replace all mystery squares of B with black squares.

To compute [bar.B], replace all mystery squares of B with white squares, unless the mystery square is preceded by a black square, in which case replace both the black square and the mystery square with a rectangle.

Example 3.9. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is on a black square. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Using the rules above to compute A, B, and the four sashes [A.bar], [bar.A], [B.bar], and [bar.B], we have:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Given an allowable dotting d of a sash C we define [I.sub.d] = [A.bar], [bar.A]] and [J.sub.d] = [SIGMA][[B.bar], [bar.B]] for [A.bar], [bar.A], [B.bar], and [bar.B] computed as above. Thus the notation [I.sub.d] [cross product] [J.sub.d] denotes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 3.10. Given C [member of] [[SIGMA].sub.n-1]:

[[SIGMA].sub.s](C) = [empty set] [cross product] C + C [cross product] [empty set] + [summation over (allowable dottings d of C)] [I.sub.d] [cross product] [J.sub.d]

References

[1] Marcelo Aguiar, Nantel Bergeron, and Frank Sottile. Combinatorial Hopf algebras and generalized Dehn-Sommerville relations. Compos. Math., 142(1):1-30, 2006.

[2] Eric Babson and Einar Steingrimsson. Generalized permutation patterns and a classification of the Mahonian statistics. Sem. Lothar. Combin., 44:Art. B44b, 18 pp. (electronic), 2000.

[3] Jean-Louis Loday and Maria O. Ronco. Hopf algebra of the planar binary trees. Adv. Math., 139(2):293-309, 1998.

[4] Claudia Malvenuto. Produits et coproduits des fonctions quasi-symetriques et de l'algebre des descentes. (LACIM), 16, 1994.

[5] Nathan Reading. Lattice congruences, fans and Hopf algebras. J. Combin. Theory Ser. A, 110(2):237-273, 2005.

[6] N. J. A. Sloane. The on-line encyclopedia of integer sequences. http://oeis.org. 2013.

Shirley Law *

Washington College, USA

* Email: slaw2@washcoll.edu.

Printer friendly Cite/link Email Feedback | |

Author: | Law, Shirley |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 6461 |

Previous Article: | Noncrossing sets and a Grassmann associahedron. |

Next Article: | A product formula for the TASEP on a ring --extended abstract. |

Topics: |