INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A06

MULTI-ORDERED POSETS

Lisa Bishop

Department of Mathematics, Occidental College, Los Angeles, CA 90041, United States

                              lbishop@oxy.edu

Kendra Killpatrick

Department of Mathematics, Pepperdine University, Malibu, CA 90263, United Stated

                     Kendra.Killpatrick@pepperdine.edu

Received: 6/6/06, Accepted: 1/29/07, Published: 2/3/07

Abstract

Richard Stanley first introduced the idea of an r-differential poset in 1988. There are two well known types of differential posets: The first is the 1-differential poset of partitions called Young’s lattice and its generalization to the k-differential k-ribbon poset, and the second is the 1-differential Fibonacci lattice Z(1) and its generalization to the r-differential Fibonacci lattice Z(r). In this paper we define a new type of poset, called a doubly-ordered poset, for which the binary operation is a combination of two binary relations on a set. This result can be extended to a set with multiple relations, called a multi-ordered poset. This paper introduces the idea of an r-differential multi-ordered poset and provides an example of such a poset that is the analogue of Young’s lattice. This analogue satisfies virtually all of the properties of Stanley’s r-differential poset.

1. Introduction

In a 1988 paper Stanley [8] introduced the concept of a differential poset, a class of partially ordered sets. The prime example of a 1-differential poset is Young’s lattice, the poset of partitions of n ordered by inclusion of the Ferrers diagram. White and Shimozono discuss the generalization of Young’s lattice and Young tableaux to the domino poset and the corresponding domino tableaux [5] and to the k-ribbon poset and corresponding k-ribbon tableaux [6]. The domino poset is known to be 2-differential and the k-ribbon poset is known to be k-differential. At this time, there are only two known classes of differential posets. The first are the k-ribbon generalizations of Young’s lattice and the second are the generalizations of the Fibonacci lattice. In his initial paper on differential posets, Stanley poses the problem to find “interesting” examples of r-differential posets and asks if there are any irreducible differential lattices besides the generalizations of Young’s lattice and the Fibonacci lattice.

In this paper we define both a doubly-ordered poset and a more general multi-ordered poset, which are “almost” differential according to Stanley’s definition and that we think are “interesting”. We define a differential doubly-ordered poset and a differential multi-ordered poset and prove which of Stanley’s conditions on differential posets apply to this new hybrid poset. As with the two standard classes of differential posets, the multi-ordered poset gives rise to many interesting questions about the number of chains in this poset and the tableau representations of these chains. We discuss these open problems in Section 6.

2. Background and Definitions

In this section we present some necessary definitions related to tableaux and posets. For a more complete exposition, the reader is referred to Stanley’s excellent book on Enumerative Combinatorics [7].

Let λ = (λ_{1}, λ_{2}, …, λ_{k}) be a k-tuple of non-negative integers. We say that λ is a partition of n if λ_{1} + λ_{2} + ⋯ + λ_{k} = n and λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} > 0.

A Ferrers diagram describes a partition λ pictorially through an array of n dots in k left-justified rows with row i containing λ_{i} dots for 1 ≤ i ≤ k. For example, the Ferrers diagram for the partition λ = (7, 5, 3, 3, 1) is:

T = \begin{matrix}• & • & • & • & • & • & • \\ • & • & • & • & • \\ • & • & • \\ • & • & • \\ • \end{matrix}

If λ is a partition and μ is a partition whose Ferrers diagram is contained in the Ferrers diagram of λ, then the skew shape λ/μ is the set of cells obtained by deleting the cells of μ from λ. For example, for λ = (5, 3, 3, 1) and μ = (4, 2, 1) then the skew shape (5, 3, 3, 1)/(4, 2, 1) looks like the following, where μ is shown by X’s:

λ/μ = \begin{matrix}X & X & X & X & • \\ X & X & • \\ X & • & • \\ • \end{matrix}

A diagonal for a tableau is any line with slope of −1 through the Ferrers diagram of that tableau.

Definition 1. A partially ordered set, or poset, is a set A together with a binary relation, ≤, such that for every a, b, c ∈ A:

1. a ≤ a,

2. a ≤ b and b ≤ a implies a = b, and

3. a ≤ b and b ≤ c implies a ≤ c

An element a in a poset P covers an element b ∈ P if b ≤ a and there is no c such that b < c < a. We will write b ⋖ a to indicate that a covers b.

We say that the poset P has a ˆ0 if there exists an element ˆ0 ∈ P such that ˆ0 ≤ x for all x ∈ P. If every interval of P is finite, then the poset P is said to be locally finite. A chain is a poset in which any two elements are comparable. The chain C in poset P is saturated if there does not exist a z ∈ P − C such that x < z < y for some x, y ∈ C. In a locally finite poset, the chain x_{0} < x_{1} < ... < x_{n} is saturated if and only if x_{i} covers x_{i−1} for 1 ≤ i ≤ n. We say that the chain x_{0} < x_{1} < ... < x_{n} is a chain of length n. A poset P is called graded if it has a minimum element ˆ0 and if for each a ∈ A all maximal chains from ˆ0 to a have the same length. We say a, b ∈ P have a greatest lower bound, or meet, if there is a c ∈ P such that c ≤ a, c ≤ b and for any d such that d ≤ a, d ≤ b, then d ≤ c. The least upper bound, or join, of a and b is defined similarly by reversing the inequalities. A poset where every pair of elements have a meet and a join is called a lattice.

In 1988 R. Stanley [8] gave the following definition of an r-differential poset.

Definition 2. An r-differential poset, P, is a poset which satisfies the following three conditions:

1. P has a ˆ0, is graded and is locally finite.

2. If x ≠ y for x, y ∈ P and there are exactly k elements in P which are covered by both x and y, then there are exactly k elements in P which cover both x and y.

3. For x ∈ P, if x covers exactly k elements of P, then x is covered by exactly k + r elements of P.

The classic example of a 1-differential poset is Young’s lattice, the poset of the set of partitions together with the binary relation λ ≤ μ if and only if λ_{i} ≤ μ_{i} for all i.

The first seven rows of Young’s lattice are shown below, with lines drawn to indicate cover relations.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∅]

3. Domino Tableaux

A domino is a pair of adjacent dots in a Ferrers diagram. If the dots lie in the same row, we will call them a horizontal domino and if they lie in the same column, we will call them a vertical domino.

A domino shape is a Ferrers diagram that can be completely divided into dominos, which we will call a tiling of the shape. For example, the partition λ = (4, 3, 3, 1, 1) can be represented by the following Ferrers diagram:

\begin{matrix}• & • & • & • \\ • & • & • \\ • & • & • \\ • \\ • \end{matrix}

This partition is a domino shape since it can be tiled by dominos as follows:

• • • • • • • • • • • •

Note that no partitions of odd numbers are domino shapes although not all partitions of even numbers are domino shapes. In addition, the tiling of a domino shape is not necessarily unique. The λ from our previous example can also be tiled as follows:

• • • • • • • • • • • •

To create a domino tableau, first tile a domino shape with dominos. Then fill the dominos with the numbers 1, 2, …, n such that the numbers in each domino are identical, each number appears in exactly one domino, and rows and columns weakly increase. For example:

5533 44 66 1 1 2 2

Again, there may be more than one domino tableau for a given domino shape and tiling.

The domino poset, D, is the set of domino shapes together with the following binary relation. For two domino shapes λ and μ with μ ⊆ λ, we say that λ covers μ, μ ⋖ λ, if λ/μ is a domino. In general, for μ ⊆ λ, μ ≤ λ in the domino poset if λ/μ can be tiled by dominos, i.e., we can obtain μ by successively removing dominos from λ, or we can obtain λ by successively adding dominos to μ.

The first four rows of the domino poset are shown below:

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ∅]

If we let Y denote Young’s lattice, then the domino poset is isomorphic to Y^{2} (see [5] for a nice description) and thus is 2-differential.

We will call a 2-core a shape from which no domino can be removed. The only 2-cores are ”stair-step” shapes in which λ = (n, n − 1, n − 2, ..., 1).

We can use the 2-cores as a base upon which to build a poset. For instance we can take the partition λ= (2, 1) as our 2-core and define our set as the set of all partitions containing (2, 1) which can be formed by successively adding either horizontal or vertical dominos to (2, 1). Here are the first three rows of a domino poset built on the 2-core λ=(2, 1):

[figure: X; X; X; •; •; •; •; X; X; X; •; •; •; •; X; X; X; •; •; •; •; X; X; X; •; •; •; •; X; X; X; •; •; •; •; X; X; X; •; •; X; X; X; •; •; X; X; X]

A domino poset constructed on a 2-core is easily shown to be isomorphic to the standard domino poset and thus is also 2-differential. The domino poset can be generalized to the k-ribbon poset. A k-ribbon is defined as k adjacent dots in the Ferrers diagram none of which lie on the same diagonal. For the binary relation ≤ in the k-ribbon poset, we say μ ≤ λ if μ ⊆ λ and λ can be formed by adding some number of k-ribbons to μ. Note that a 2-ribbon is simply a domino. Below is an example of a 5-ribbon shape:

• • • • • • • • • • • • • • •

A k-core is a shape from which no k-ribbon can be removed and it is well known that both the k-ribbon poset and any k-ribbon poset built on a k-core are k-differential. As with domino tableaux, a k-ribbon tableaux can be created by filling each ribbon with the numbers 1, 2, …, n such that the numbers in each ribbon are identical, each number appears in exactly one ribbon, and rows and columns weakly increase. Below is an example of a 5-ribbon tableau:

2221 22 33 3 3 1 1 1 1 3

4. Doubly-Ordered Posets

We now use the standard idea of a poset to create a new object called a doubly-ordered poset.

Definition 3. A doubly-ordered poset A is a set together with a binary relation ≤ that is composed of two binary relations ≤_{1}, ≤_{2}. For x, y ∈ A, x ≤ y if there exists a set of elements x_{1}, x_{2}, ..., x_{k−1} such that x = x_{0} ≤ x_{1} ≤ x_{2} ≤ ... ≤ x_{k−1} ≤ x_{k} = y where, for each i between 1 and k, x_{i} ≤_{1} x_{i+1} or x_{i} ≤_{2} x_{i+1}. We will say that x covers y, denoted by x ⋖ y, if x is covered by y in either the ≤_{1} relation or the ≤_{2} relation, i.e. if x ⋖_{1} y or x ⋖_{2} y. We will denote this poset by A_{≤_{1},≤_{2}}.

This is a poset since the binary relation ≤ satisfies the three properties of reflexive, antisymmetric and transitive. The idea of a cover relation for this poset is slightly different than the usual definition of a cover relation since it is possible for x ⋖_{2} y and for there to exist a z such that x <_{1} z <_{1} y.

Definition 4. If Y is the set of all partitions, then Y_{≤_{1},≤_{k}}, k > 1, is the doubly-ordered poset where ≤_{1} is the usual relation in Young’s lattice and ≤_{k} is given by μ ≤_{k} λ if λ is obtained from μ by adding some number of k-ribbons.

The basic example of a doubly-ordered poset is Y_{≤_{1},≤_{2}}. Note that Y_{≤_{1}} is Young’s lattice. The doubly-ordered poset combines the two relations ≤_{1}, ≤_{2}. However Y_{≤_{2}} is not the domino poset because we allow for domino relations to exist between non-domino shapes and Y_{≤_{2}} does not by itself have a zero element. Here are the first five rows of Y_{≤_{2}}:

• • • • • • • • • • • • • • • • • • • •

• • • • • • • • •

• • • •

•

∅

The first seven rows of Y_{≤_{1},≤_{2}} are shown below, where straight lines indicate a relation in Young’s lattice, the ≤_{1} relation, and curved lines indicate a relation in Y_{≤_{2}}:

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

[figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure]

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •

[figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure] [figure]

• • • • • • • • • • • • • • • • • • • •

[figure] [figure] [figure] [figure] [figure] [figure] • • • • • • • • • [figure] [figure] [figure] [figure]

• • • •

•

[figure] [figure]

∅

The doubly-ordered poset Y_{≤_{1},≤_{k}} forms a lattice since Y_{≤_{1},≤_{k}} contains the ≤_{1} relation and thus any two elements have a meet and a join.

We now present the definition of a differential doubly-ordered poset which is similar to a differential poset.

Definition 5. An r-differential doubly-ordered poset A_{≤_{1},≤_{k}}, where r = 1 + k, is a doublyordered poset that satisfies the following three conditions:

1. A_{≤_{1},≤_{k}} has a ˆ0 and is locally finite.

2. If x ≠ y for x, y ∈ A_{≤_{1},≤_{k}}, and x and y jointly cover m elements, then for each element jointly covered by x and y either:

(a) There exists a λ, λ ≠ x and λ ≠ y, which jointly covers x and y, or

(b) One of x or y is the join of x and y.

3. For x ∈ A_{≤_{1},≤_{k}}, if x covers exactly m elements of A_{≤_{1},≤_{k}}, then x is covered by exactly m + r elements of A_{≤_{1},≤_{k}} where r = 1 + k.

Theorem 1. The doubly-ordered poset Y_{≤_{1},≤_{k}} is a k+1-differential doubly-ordered poset.

Proof. By construction Y_{≤_{1},≤_{2}} has a ˆ0 and is locally finite. The standard definition of an r-differential poset also imposes the condition of being graded. However, the doubly-ordered posets Y_{≤_{1},≤_{2}} are not graded by the definition, although a grading can be imposed. For a ∈ Y_{≤_{1},≤_{k}} not all maximal chains from ˆ0 to a have the same length. For example, the following two chains are saturated in Y_{≤_{1}≤_{2}} since each edge represents a cover relation, but one has length 3, and one has length 2.

•• • ≤_{1} •• ≤_{1} • ˆ0 ≤_{1}  • • • ≤_{1} •• ≤_{2} ˆ0

Since this poset is not graded, we will impose a grading by defining the rank of any element λ in Y_{≤_{1},≤_{2}} to be n where λ is a partition of n.

The second criteria claims that if x and y ∈ Y_{≤_{1},≤_{k}} jointly cover m elements, then there exists a unique λ, for each element, which jointly covers x and y, or one of x or y is the join of x and y. It is important to note that for Y_{≤_{1},≤_{k}} the only possible values for m are 0, 1, or 2. There are three cases.

Case 1: If x and y do not jointly cover any shapes then there is no shape λ which covers them.

This is clear by inspection.

Case 2: If μ ⋖_{1} x and μ ⋖_{1} y, or μ ⋖_{k} x and μ ⋖_{k} y then we can appeal to the underlying relations to show that there exists a λ_{1} where x ⋖_{1} λ_{1} and y ⋖_{1} λ_{1}, or there exists a λ_{2} where x ⋖_{k} λ_{2} and y ⋖_{k} λ_{2}. Since every ≤_{k} relation is k-differential this condition holds in each individual relation. It is possible in this case that λ ⋖_{1} x, λ ⋖_{1} y and μ ⋖_{k} x and μ ⋖_{k} y so that x and y jointly cover two elements. In this case there is a unique λ which covers x and y in each relation yielding the two distinct elements which cover x and y.

Case 3: Without loss of generality let x be a partition of n and y be a partition of p with n < p and μ ⋖_{1} x and μ ⋖_{k} y. In this case x differs from μ by a single dot r_{1} and y differs from μ by an k-ribbon, r_{k}. If r_{1} and r_{k} overlap, then x ≤_{1} y. If x and y are related in the ≤_{1} relation then there exists some path P_{k−1} of length k − 1 in Young’s lattice which connect x and y. Thus y is the smallest shape which covers both x and y, and is therefore the join of x and y. See the Figure below on the left for an example with k=6.

If r_{1} doesn’t overlap with r_{k} then the unique shape which covers both x and y is the union of x and y. See the figure below on the right for an example with k=6.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ≤_{6}; ≤_{1}; P_{5}; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ≤_{1}; ≤_{6}; ≤_{6}; ≤_{1}]

The third criteria is clear by looking at each relation separately. Let λ be an element of Y_{≤_{1},≤_{k}}, where λ covers m = n + p elements, n elements through relation ≤_{1} and p elements through relation ≤_{k}. Since we know that ≤_{1} is 1-differential we can say that λ is covered by n + 1 elements through the ≤_{1} relation. Since we know that the k-ribbon poset built on any shape is k-differential we can say that λ is covered by p + k elements through the ≤_{k} relation. Thus, if λ covers n + p elements, it covers n + 1 + p + k elements and thus is k + 1-differential.

5. Multi-Ordered Poset

We can now extend the idea of a doubly-ordered poset to that of a multi-ordered poset.

Definition 6. A multi-ordered poset is a set A, together with n > 1 binary relations ≤_{1}, ≤_{2}, ≤_{3}, …, ≤_{n}. For x, y ∈ A, we will say x ≤ y if there exists a set of elements x_{1}, x_{2}, ..., x_{m−1} such that x = x_{0} ≤ x_{1} ≤ x_{2} ≤ ⋯ ≤ x_{m−1} ≤ x_{m} = y where for each i between 1 and m, x_{i} ≤_{k} x_{i+1} for some 1 ≤ k ≤ n. We will say that x ⋖ y if x ⋖_{k} y for some 1 ≤ k ≤ n. We will denote the multi-ordered poset by A_{≤_{1},≤_{2},...,≤_{n}}.

For a specific example of a multi-ordered poset, we have the following definition:

Definition 7. If Y is the set of all partitions, then Y_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}}, 1 < k_{1} < k_{2} < ... < k_{n}, is the multi-ordered poset where ≤_{k_{j}} is the relation given by μ ≤_{k_{j}} λ if λ is obtained from μ by adding k_{j}-ribbons.

Note, again, that the usual ≤_{1} relation of Young’s lattice is required for the multi-ordered poset Y_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}}.

Definition 8. An r-differential multi-ordered poset A_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}}, 1 < k_{1} < k_{2} < ... < k_{n}, where r = 1 + k_{1} + k_{2} + ... + k_{n}, is a multi-ordered poset that satisfies the following three conditions:

1. A_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}} has a ˆ0 and is locally finite.

2. If x ≠ y for x, y ∈ A_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}} and x and y jointly cover m elements, then for each element jointly covered by x and y either:

(a) There exists a λ, λ ≠ x and λ ≠ y, which jointly covers x and y, or

(b) One of x or y is the join of x and y.

3. For x ∈ A_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}}, if x covers exactly k elements of A_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}}, then x is covered by exactly k + r elements of A_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}} where r = 1 + k_{1} + k_{2} + ... + k_{n}.

Theorem 2. The multi-ordered poset Y_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}} is an r-differential multi-ordered poset where r = 1 + k_{1} + k_{2} + ... + k_{n}.

Proof. The poset Y_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}} has a zero element by construction and is clearly locally finite.

To prove the second condition, there are two cases:

Case 1: If μ ⋖_{1} x and μ ⋖_{1} y or μ ⋖_{k_{i}} x and μ ⋖_{k_{i}} y, for 1 ≤ i ≤ n, then we can appeal to the underlying ≤_{1} or ≤_{k_{i}} relations to show that there exists a λ, where x ⋖_{1} λ and y ⋖_{1} λ or x ⋖_{k_{i}} λ and y ⋖_{k_{i}} λ, which covers both x and y. Since the underlying ≤_{1} and ≤_{k_{i}} relations are 1-differential and k_{i}-differential respectively, this condition holds for each case where x and y cover an element μ through the same relation.

Case 2: Suppose μ ⋖_{j} x and μ ⋖_{l} y, for 1 ≤ j < l ≤ k_{n}. We know that x differs from μ by a j-ribbon, r_{j}, and y differs from μ by an l-ribbon, r_{l}. If r_{j} and r_{l} do not overlap, then λ, the union of x and y, will jointly cover x and y.

Suppose r_{j} and r_{l} overlap in m cells. If m = j, then r_{j} is contained in r_{l}. Then there is a path, P_{l−j}, in Young’s lattice of length l − j from x to y, and y is the join of x and y. If m < j we will let o_{m} denote these m overlapping cells. Let b denote the cell in o_{m} that is the leftmost cell in the lowest row of o_{m} and let t denote the cell in o_{m} that is the rightmost cell in the uppermost row of o_{m}. Since b is the end of the r_{l} ribbon, then the cell immediately below if must belong to r_{j}, otherwise r_{l} would not be a valid ribbon to add to μ. Similarly, since t is the end of the r_{j} ribbon, the cell immediately to the right of t must belong to r_{l}, otherwise r_{j} would not be a valid ribbon to add to μ. By definition, each cell in the ribbon o_{m} has no cell below and to the right of it along its diagonal in the partition. We create λ by taking the union of x and y plus the m cells which lie immediately below and to the right of each of the overlapping cells along the diagonal. Each of these cells are available and since we have determined that when moving b there will be a cell in the partition to the left of it and when we move t there will be a cell in the partition above it then we have created a valid partition shape. Below is an example of this overlapping case. Thus given any x, y which jointly cover a shape μ, we can find a shape λ which jointly covers x, y.

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; ≤_{6}; ≤_{7}; ≤_{7}; ≤_{6}]

For the third condition, we can again appeal to the fact that the ≤_{1} relation is 1differential and each of the individual ≤_{k_{i}} relations is k_{i}-differential. Let λ be an element of Y_{≤_{1},≤_{k_{1}},≤_{k_{2}},...,≤_{kn}} and suppose λ covers n+p_{1} +p_{2} +⋯+p_{n} elements, n elements through the ≤_{1} relation and p_{i} elements through the ≤_{k_{i}} relation. Then λ is covered by n + 1 elements through the ≤_{1} relation and p_{i} + k_{i} elements through the ≤_{k_{i}} relation. Thus λ is covered by n + p_{1} + p_{2} + ⋯ + p_{n} + 1 + k_{1} + k_{2} + ⋯ + k_{n} elements.

6. Further Research

There are several interesting combinatorial results of r-differential posets which could potentially be extended to multi-ordered posets. These extensions are a source of numerous further research opportunities.

Stanley proved that for any r-differential poset r^{n}n! = ∑_{λ∈P} e(λ)^{2}, where e(λ) is the number of chains in P from ˆ0 to λ. We can interpret this equation combinatorially as a bijection between r-colored permutations of the numbers 1 through n and pairs of chains (P, Q) in the r-differential poset from ˆ0 to λ for λ an element at height n. For r = 1 we have the well-known Schensted correspondence which outlines this bijection. For r = 2 we have the domino insertion of Barbasch and Vogan [1] and Garfinkle [2]. For r > 2 we have the k-ribbon insertion of Shimozono and White [6]. We conjecture that there is a similar formula and bijection for Y_{≤_{1},≤_{2}} and for doubly-ordered posets in general and are working towards the formulation of such a statement.

For r-differential posets, a chain in the poset from ˆ0 to n can be represented as a tableau. Thus, the number of chains from ˆ0 to λ for a specific λ is the same as the number of tableaux of shape λ. A chain in Y_{≤_{1},≤_{2}} from ˆ0 to λ can be represented by a tableau with some number of dominos in it. For Young’s lattice, the well-known Hook Formula of Frame-Robinson-Thrall gives the number of standard young tableaux of shape λ. A related problem for doubly-ordered posets would be to develop a method of counting the number of standard tableaux of a given shape λ containing a specified number of dominos. More generally, one could ask whether there is a hook formula of some sort for counting the number of standard tableaux containing k_{1} single cells, k_{2} dominos, k_{3} 3-ribbons, …, and k_{n} n-ribbons.

Acknowledgements

The authors wish to thank Naiomi Cameron for her helpful comments during the development of the ideas for this paper and for her thoughtful editing throughout the process.

References

[1] D. Barbasch and D. Vogan, Primitive Ideals and Orbital Integrals on Complex Classical Groups, Math. Ann. 259 (1982) 153-199.

[2] D. Garfinkle, On the Classification of Primitive Ideals of Complex Classical Lie Algebras, I, Compositio Mathematica 75 (1990) 135-169.

[3] D. E. Littlewood, Modular representations of symmetric groups, Proc. Royal Soc. London Ser. A, 209 (1951), pp. 333-353.

[4] B. Sagan, The Symmetric Group, 2^{nd} Edition, Springer-Verlag, New York, NY, 2001.

[5] M. Shimozono and D. White, A Color-to-Spin Domino Schensted Algorithm, The Electronic Journal of Combinatorics, Volume 8, 2001.

[6] M. Shimozono and D. White, Color-to-Spin Ribbon Schensted Algorithms, Discrete Mathematics 246 (2002) 295-316.

[7] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge, 1999.

[8] R. Stanley, Differential Posets, Journal of the American Mathematical Society, Volume 1, Number 4, October 1988, 919–961.