Updown categories

Michael E. Hoffman

Dept. of Mathematics, U. S. Naval Academy Annapolis, MD 21402 USA and Max-Planck-Institut für Mathematik Vivatsgasse 7, D-53111 Bonn, Germany

                             meh@usna.edu

February 25, 2004

Keywords: category, poset, differential poset, universal cover, partitions, rooted trees MR Classifications: Primary 18B35, 06A07; Secondary 05A17, 05C05

Abstract

A poset can be regarded as a category in which there is at most one morphism between objects, and such that at most one of Hom(c, c′) and Hom(c′, c) is nonempty for c ≠ c′. If we keep in place the latter axiom but allow for more than one morphism between objects, we can have a sort of generalized poset in which there are multiplicities attached to the covering relations, and possibly nontrivial automorphism groups. We call such a category an “updown category.” In this paper we give a precise definition of such categories and develop a theory for them, which incorporates earlier notions of differential posets and weighted-relation posets. We also give a detailed account of ten examples, including the updown posets of integer partitions, integer compositions, planar rooted trees, and rooted trees.

1 Introduction

Suppose we have a set P of combinatorial objects, for example rooted trees, which naturally form a ranked poset (for rooted trees, the ranking is by the number of non-root vertices). Each object of P can be constructed in steps from a basic object in rank 0, and p covers q in the partial order if p can be built from q in one step. (For rooted trees, the “basic object” is the one-vertex tree, and the building-up process consists of adding a new edge and terminal vertex to some existing vertex.) In this situation, there are naturally two sets of multiplicities on the covering relations of P: the number of ways to build up p from q is u(q; p), and the number of ways to tear down p to get q is d(q; p). (For example, for rooted trees p, q with p covering q, u(q; p) is the number of distinct vertices of q to which a new edge and terminal vertex can be added to get p, while d(q; p) is the number of distinct terminal edges of p that, when removed, leave q.) These multiplicities may be distinct, as in the case of rooted trees (studied in detail in [4]), and the difference is related to the automorphism groups of objects of P.

Now a poset can be thought of as a category with at most one morphism between objects, and at most one of the sets Hom(c, c′) and Hom(c′, c) nonempty when c ≠ c′. If we relax the the first of these conditions, we allow for multiplicities (if c ≠ c′) and automorphisms (if c = c′.). In §2 we give a precise definition of an updown category, which allows us to formalize the notions of the previous paragraph. We also define a morphism between updown categories, as well as products of updown categories. For any updown category 𝒞, we define “up” and “down” operators U and D on the free vector space 𝕜(Ob 𝒞), 𝕜 a field of characteristic 0.

In [3] a theory of universal covers was developed for weighted-relation posets, i.e., ranked posets in which each covering relation has a single number n(x, y) assigned to it. The universal cover of a weighted-relation poset P is the “unfolding” of P into a usually much larger weighted-relation poset P̃, so that the Hasse diagram of P̃ is a tree and all covering relations of P̃ have multiplicity 1. Although the description of P̃ had a natural description in each of the seven examples considered in [3], the general construction of P̃ given in [3, Theorem 3.3] was somewhat unsatisfactory since it involved many arbitrary choices. In §3 we study unilateral updown categories (i.e., updown categories with trivial automorphism groups): these are essentially “categorified” weighted-relation posets, and the universal-cover construction (Proposition 3.3 below) is much more natural in this setting.

In [10, 11] Stanley developed a theory of differential posets. Some ideas of this theory were extended to the case of rooted trees in [4]. In §4 we offer a more general view of “commutation conditions” that may be satisfied by the operators U and D defined in §2 for any updown category.

The theory developed here is somewhat similar to Fomin’s theory of duality of graded graphs [1, 2], but is both more restrictive and more general: more restrictive in that the functions u(p; q) and d(p; q) must give rise to the same partial order, i.e., for any pair p, q we have u(p; q) = 0 if and only if d(p; q) = 0; and more general in that we consider weaker commutation conditions than he does.

In §5 we offer ten examples, which include all those given in [3]. These include the posets of monomials, necklaces, integer partitions, integer compositions, and both planar rooted trees and rooted trees.

The basic idea of this paper was conceived during the academic year 2002-2003, when the author was partially supported by the Naval Academy Research Council. This paper was written during a stay at the Max-Planck-Institut für Mathematik during the following academic year, while the author was on sabbatical leave from the Naval Academy. The author thanks both the Academy and the Institut for their support.

2 Updown categories

We begin by defining an updown category.

Definition 2.1. An updown category is a small category 𝒞 with a rank functor |·| : 𝒞 → ℕ (where ℕ is the ordered set of natural numbers regarded as a category) such that

A1. Each level 𝒞_{n} = {p ∈ Ob 𝒞 : |p| = n} is finite.

A2. The zeroth level 𝒞_{0} consists of a single object ˆ0, and Hom(ˆ0, p) is nonempty for all objects p of 𝒞.

A3. For objects p, p′ of 𝒞, Hom(p, p′) is always finite, and Hom(p, p′) = ∅ unless |p| < |p′| or p = p′. In the latter case, Hom(p, p) is a group, denoted Aut(p).

A4. Any morphism p → p′, where |p′| = |p| + k, factors as a composition p = p_{0} → p_{1} → ⋯ → p_{k} = p′, where |p_{i+1}| = |p_{i}| + 1;

A5. If |p′| = |p| + 1, the actions of Aut(p) and Aut(p′) on Hom(p, p′) (by precomposition and postcomposition respectively) are free.

Given an updown category, we can define the multiplicities mentioned in the introduction as follows. Definition 2.2. For any two objects p, p′ of an updown category 𝒞 with |p′| = |p| + 1, define

u(p; p′) = |Hom(p, p′)/ Aut(p′)| = \frac{| Hom(p, p′)|}{| Aut(p′)|}

and

d(p; p′) = |Hom(p, p′)/ Aut(p)| = \frac{| Hom(p, p′)|}{| Aut(p)|}.

It follows immediately from these definitions that

u(p; p′)| Aut(p′)| = d(p; p′)| Aut(p)|.  (1)

We note two extreme cases. First, suppose 𝒞_{n} is empty for all n > 0. Then 𝒞 is essentially the finite group Aut ˆ0. Second, suppose that every set Hom(p, p′) has at most one element. Then 𝒞 is a ranked poset with least element ˆ0.

Two important special types of updown categories are defined as follows Definition 2.3. An updown category 𝒞 is unilateral if Aut(p) is trivial for all p ∈ Ob 𝒞. An updown category 𝒞 is simple if Hom(c, c′) has at most one element for all c, c′ ∈ Ob 𝒞, and the factorization in A4 is unique, i.e., for |c′| > |c| any f ∈ Hom(c, c′) has a unique factorization into morphisms between adjacent levels.

Of course simple implies unilateral, but not conversely. A unilateral updown category is the “categorification” of a weighted-relation poset in the sense of [3]; see the next section for details.

If 𝒞 and 𝒟 are updown categories, their product 𝒞×𝒟 is the usual one, i.e. Ob(𝒞×𝒟) = Ob 𝒞 × Ob 𝒟 and

Hom_{𝒞×𝒟} ((c, d), (c′, d′)) = Hom_{𝒞}(c, c′) × Hom_{𝒟} (d, d′).

The rank is defined on 𝒞 × 𝒟 by |(c, d)| = |c| + |d|. We have the following result.

Proposition 2.1. If 𝒞 and 𝒟 are updown categories, then so is their product 𝒞 × 𝒟.

Proof. Since

(𝒞 × 𝒟)_{n} = ∐_{i+j=n} 𝒞_{i} × 𝒟_{j},

axiom A1 is clear; and evidently ˆ0 = (ˆ0_{𝒞}, ˆ0_{𝒟} ) satisfies A2. Checking A3 is routine, and for A4 we can combine factorizations

c = c_{0} → c_{1} → ⋯ → c_{k} = c′ and d = d_{0} → d_{1} → ⋯ → d_{l} = d′

into

(c, d) → (c_{1}, d) → ⋯ → (c′, d) → (c′, d_{1}) → ⋯ → (c′, d′).

Finally, for A5 note that, e.g.,

Hom((c, d), (c′, d)) ≅ Hom(c, c′) × Aut(d),

and the action of Aut(c, d) ≅ Aut(c) × Aut(d) on this set is free if and only if the action of Aut(c) on Hom(c, c′) is free.

We note that the product of two unilateral categories is unilateral, but the product of simple categories need not be simple: see Example 2 in §5 below. We now define a morphism of updown categories. Definition 2.4. Let 𝒞, 𝒟 be updown categories. A morphism from 𝒞 to 𝒟 is a functor F : 𝒞 → 𝒟 with |F (p)| = |p| for all p ∈ Ob 𝒞, and such that, for any p, q ∈ Ob 𝒞 with |q| = |p| + 1, the induced maps

Aut(p, p) → Aut(F (p), F (p)),

∐_{{q′:F (q′)=F (q)}} Hom(p, q′)/ Aut(p) → Hom(F (p), F (q))/ Aut(F (p)),

and

∐_{{q′:F (q′)=F (q)}} Hom(p, q′)/ Aut(q′) → Hom(F (p), F (q))/ Aut(F (q))

are injective.

We have the following result.

Proposition 2.2. Suppose F : 𝒞 → 𝒟 is a morphism of updown categories. If 𝒟 is unilateral, then so is 𝒞; if 𝒟 is simple, then 𝒞 is also simple and F is injective as a function on object sets.

Proof. It follows immediately from Definition 2.4 that 𝒞 must be unilateral when 𝒟 is. Now suppose 𝒟 is simple. Then 𝒞 is unilateral, and it follows from Definition 2.4 that the induced function

∐_{{q′:F (q′)=F (q)}} Hom(p, q′) → Hom(F (p), F (q))

is injective when |q| = |p| + 1: but Hom(F (p), F (q)) is (at most) a one-element set, so F must be injective on object sets and Hom(p, q) can have at most one object. But then unique factorization of morphisms in 𝒞 follows from that in 𝒟, so 𝒞 is simple.

One can verify that there is a morphism of updown categories 𝒞 → 𝒞 × 𝒟 given by sending c ∈ Ob 𝒞 to (c, ˆ0_{𝒟} ) whenever 𝒞 and 𝒟 are updown categories; similarly there is a morphism 𝒟 → 𝒞 × 𝒟. We denote the n-fold cartesian power of 𝒞 by 𝒞^{n}.

Let 𝕜 be a field of characteristic 0, 𝕜(Ob 𝒞) the free vector space on Ob 𝒞 over 𝕜. We now define “up” and “down” operators on 𝕜(Ob 𝒞). Definition 2.5. For an updown category 𝒞, let U, D : 𝕜(Ob 𝒞) → 𝕜(Ob 𝒞) be the the linear operators given by

Up = ∑_{|p′|=|p|+1} u(p; p′)p′

and

Dp = \begin{cases}∑_{|p′|=|p|−1} d(p′; p)p′, & |p| > 0, \\ 0, & p = ˆ0, \end{cases}

for all p ∈ Ob 𝒞.

Proposition 2.3. The operators U and D are adjoint with respect to the inner product on 𝕜(Ob 𝒞) defined by

⟨p, p′⟩ = \begin{cases}| Aut(p)|, & if p′ = p, \\ 0, & otherwise. \end{cases}

Proof. Since ⟨Up, p′⟩ = ⟨p, Dp′⟩ = 0 unless |p′| = |p| + 1, it suffices to consider that case. Then

⟨Up, p′⟩ = u(p; p′)⟨p′, p′⟩ = u(p; p′)| Aut(p′)|

while

⟨p, Dp′⟩ = d(p; p′)⟨p, p⟩ = d(p; p′)| Aut(p)|,

and the two agree by equation (1).

Now we extend the definitions of u(p; p′) and d(p; p′) to any pair p, p′ ∈ Ob 𝒞 by setting u(p; p′) = d(p; p′) = 0 if Hom(p, p′) = ∅ and

u(p; p′) = \frac{⟨U^{|p′|−|p|}(p), p′⟩}{| Aut(p′)|}, d(p; p′) = \frac{⟨U^{|p′|−|p|}(p), p′⟩}{| Aut(p)|}

otherwise. It is immediate that equation (1) still holds, and that

U^{k}(p) = ∑_{|p′|=|p|+k} u(p; p′)p′

and

D^{k}(p) = ∑_{|p′|=|p|−k} d(p; p′)p′

for any p ∈ Ob 𝒞. (However, it is no longer true that u(p; q) and d(p; q) have any simple relation to | Hom(p, q)| when |q| − |p| > 1.) An important special case of the extended equation (1) is

\frac{d(ˆ0; p)}{u(ˆ0; p)} = \frac{| Aut(p)|}{| Aut ˆ0|}  (2)

for any object p of 𝒞. If Aut ˆ0 is trivial (as in all the examples of §5 below), equation (2) gives the order of the automorphism group of p ∈ Ob 𝒞 as a ratio of multiplicities (cf. Proposition 2.6 of [4]). We also have the following result.

Proposition 2.4. If |p| ≤ k ≤ |q|, then

u(p; q) = ∑_{|p′|=k} u(p; p′)u(p′; q),

and similarly for u replaced by d.

Proof. We have

u(p; q) = \frac{⟨U^{|q|−|p|}p, q⟩}{| Aut(q)|}

= \frac{1}{| Aut(q)|}⟨U^{k−|p|}U^{|q|−k}(p), q⟩

= \frac{1}{| Aut(q)|} ∑_{|p′|=k} u(p; p′)⟨U^{k−|p|}p′, q⟩

= \frac{1}{| Aut(q)|} ∑_{|p′|=k} u(p; p′)u(p′; q)| Aut(q)|

= ∑_{|p′|=k} u(p; p′)u(p′; q),

and the proof for d is similar.

Definition 2.6. For an updown category 𝒞, define the induced partial order on Ob 𝒞 by setting p ⪯ q if and only if Hom(p, q) ≠ ∅.

It follows from Proposition 2.4 that p ⪯ q ⟺ u(p; q) ≠ 0 ⟺ d(p; q) ≠ 0. Henceforth we write p ⊲ q if q covers p in the induced partial order.

In the unilateral case, equation (2) is trivial since u(p; q) = d(p; q) for all p and q. Nevertheless, we have the following interpretation of the multiplicity in this case.

Proposition 2.5. Let 𝒞 be a unilateral updown category, p, q ∈ Ob 𝒞 with |q|−|p| = n > 0. Then u(p; q) = d(p; q) is the number of distinct chains (h_{1}, …, h_{n}) so that each h_{i} is a morphism between adjacent levels and h_{n}h_{n−1} ⋯ h_{1} is a morphism from p to q.

Proof. We use induction on n. The result is immediate if n = 1, since in a unilateral updown category

u(p; q) = d(p; q) = | Hom(p, q)|

when |q| = |p| + 1. Now if N(p, q) denotes the number of chains (h_{1}, …, h_{n}) as in the statement of the proposition, it is evident that, for |q| > |p| + 1,

N(p, q) = ∑_{r⊲q}N(p, r)N(r, q).

But then the inductive step follows from Proposition 2.4.

3 Weighted-Relation Posets and Unilateral Updown Categories

Let 𝔘 be the category of updown categories, 𝔘𝔘 the full subcategory of unilateral updown categories. For a functor F between unilateral updown categories 𝒞, 𝒟, Definition 2.4 reduces to the requirement that F preserve rank and that the induced function

∐_{{q′:F (q′)=F (q)}} Hom(p, q′) → Hom(F (p), F (q))  (3)

be injective whenever p, q ∈ Ob 𝒞 with |q| = |p| + 1.

The notion of a weighted-relation poset was defined in [3]. This consists of a ranked poset

P = ⋃_{n≥0} P_{n}

with a least element ˆ0 ∈ P_{0}, together with nonnegative integers n(x, y) for each x, y ∈ P so that n(x, y) = 0 unless x ⪯ y, and

n(x, y) = ∑_{|z|=k} n(x, z)n(z, y)  (4)

whenever |x| ≤ k ≤ |y|. A morphism of weighted-relation posets P, Q is a rank-preserving map f : P → Q such that

n(f(t), f(s)) ≥ ∑_{s′∈f^{−1}(f(s))} n(t, s′)  (5)

for any s, t ∈ P with |s| = |t| + 1. Let 𝔚 be the category of weighted-relation posets.

Given an updown category 𝒞, it follows from Proposition 2.4 that the weight functions n(x, y) = u(x; y) and n(x, y) = d(x; y) on the poset Ob 𝒞 (with the partial order defined by Definition 2.6) both satisfy equation (4). So we have two weighted-relation posets based on Ob 𝒞 corresponding to these two sets of weights. In fact, we can describe them functorially.

If 𝒞 is an updown category, we can form a unilateral updown category 𝒞^{↑} with Ob 𝒞^{↑} = Ob 𝒞, and with Hom_{𝒞^{↑}}(p, p′) defined as follows. We declare Hom_{𝒞^{↑}}(p, p) = Aut_{𝒞^{↑}}(p) trivial for all p, and for |p′| > |p| we define Hom_{𝒞^{↑}}(p, p′) to be the set Hom_{𝒞}(p, p′) with the equivalence relation generated by declaring, for any factorization f = f_{n}f_{n−1} ⋯ f_{1} of f ∈ Hom_{𝒞}(p, p′) into morphisms between adjacent levels, f equivalent to α_{n}f_{n} ⋯ α_{1}f_{1}, where α_{i} ∈ Aut(trg f_{i}). It is routine to check that 𝒞^{↑} satisfies the axioms of an updown category, and for p, p′ ∈ Ob 𝒞 with |p′| = |p| + 1 the multiplicity is

| Hom_{𝒞^{↑}}(p, p′)| = |Hom_{𝒞}(p, p′)/ Aut_{𝒞}(p′)| = u(p; p′).

Of course 𝒞^{↑} coincides with 𝒞 if 𝒞 is unilateral.

Similarly, for any updown category 𝒞 there is a unilateral updown category 𝒞^{↓} with Ob 𝒞^{↓} = Ob 𝒞, trivial automorphisms, and Hom_{𝒞^{↓}}(p, p′) the set Hom_{𝒞}(p, p′) with the equivalence relation f ∼ f_{n}β_{n}f_{n−1} ⋯ f_{1}β_{1} for f = f_{n}f_{n−1} ⋯ f_{1} a factorization of f ∈ Hom_{𝒞}(p, p′) into morphisms between adjacent levels and β_{i} ∈ Aut(src f_{i}). Then

| Hom_{𝒞^{↓}}(p, p′)| = |Hom_{𝒞}(p, p′)/ Aut_{𝒞}(p)| = d(p; p′)

for p, p′ ∈ Ob 𝒞 with |p′| = |p| + 1. We have the following result.

Proposition 3.1. There are two functors 𝔘 → 𝔘𝔘, taking an updown category 𝒞 to 𝒞^{↑} and 𝒞^{↓} respectively.

Proof. We first consider the “up” functor. For a morphism F : 𝒞 → 𝒟 of updown categories, we must produce a morphism F^{↑} : 𝒞^{↑} → 𝒟^{↑} of unilateral updown categories. But given such a functor F, Definition 2.4 requires that F preserve rank and that the induced function

∐_{{q′:F (q′)=F (q)}} Hom(p, q′)/ Aut(p′) → Hom(F (p), F (q))/ Aut(F (q))

be injective for all p, q ∈ Ob 𝒞 with |q| = |p| + 1. This is exactly the statement that the induced functor F^{↑} is a morphism of unilateral updown categories. The proof for the “down” functor is similar.

Now we pass from unilateral updown categories to weighted-relation posets.

Proposition 3.2. There is a functor W rp : 𝔘𝔘 → 𝔚, sending a unilateral updown category 𝒞 to the set Ob 𝒞 with the partial order of Definition 2.5 and the weight function n(x, y) = u(x; y) = d(x; y).

Proof. The only thing to check is the morphisms. Suppose F : 𝒞 → 𝒟 is a morphism of 𝔘𝔘. Then F defines a function on the object sets, and the function (3) is injective. Hence

∑_{{q′:F (q′)=F (q)}} | Hom(p, q′)| ≤ | Hom(F (p), F (q))|

and so (since, e.g., n(p, q′) = | Hom(p, q′)|), inequality (5) holds and F induces a morphism of weighted-relation posets.

As defined in [3], a morphism f : P → Q of weighted-relation posets is a covering map if f is surjective and the inequality (5) is an equality. A universal cover P̃ of P is a cover P̃ → P such that, if P′ → P is any other cover, then there is a covering map P̃ → P′ so that the composition P̃ → P′ → P is the cover P̃ → P. In [3] such a universal cover was constructed for any weighted-relation poset P.

In fact, the construction of [3] can be made considerably simpler and more natural if we work instead with unilateral updown categories. We first categorify the definition of covering map.

Definition 3.1. A morphism π : 𝒞′ → 𝒞 of unilateral updown categories is a covering map if π is surjective on the object sets and the induced function

∐_{{q′:π(q′)=π(q)}} Hom(p, q′) → Hom(π(p), π(q))  (6)

is a bijection for all p, q ∈ Ob 𝒞′ with |q| = |p| + 1.

Then we have the following result.

Proposition 3.3. Every unilateral updown category 𝒞 has a universal cover 𝒞̃.

Proof. We define 𝒞̃ to be the category whose level-n objects are strings (f_{1}, f_{2}, …, f_{n}) of morphisms f_{i} ∈ Hom(c_{i−1}, c_{i}), where c_{i} ∈ 𝒞_{i}, and whose morphisms are just inclusions of strings. It is straightforward to verify that 𝒞̃ is a unilateral updown category (with ˆ0𝒞̃ the empty string). Define the functor π : 𝒞̃ → 𝒞 by sending the empty string to ˆ0 ∈ Ob 𝒞, the nonempty string (f_{1}, …, f_{n}) of 𝒞̃ to the target of f_{n} in Ob 𝒞, and the inclusion (f_{1}, …, f_{j}) ⊂ (f_{1}, …, f_{n}) to the morphism f_{n}f_{n−1} ⋯ f_{j+1} ∈ Hom(c_{j}, c_{n}). That the induced function (6) is a bijection is a tautology.

Now let P : 𝒞′ → 𝒞 be another cover of 𝒞: we must define a covering map F : 𝒞̃ → 𝒞′ of unilateral updown categories so that π = P F. We proceed by induction on level: evidently we can get started by sending the empty string in 𝒞̃_{0} to the element ˆ0 of 𝒞′. Suppose F is defined through level n−1, and consider a level-n object (f_{1}, …, f_{n}) of 𝒞̃. Let c_{n} = π(f_{1}, …, f_{n}). By the induction hypothesis we have c′_{n−1} = F (f_{1}, …, f_{n−1}) ∈ Ob 𝒞′, and c_{n−1} = P (c′_{n−1}) is the target of f_{n−1}, hence the source of f_{n}. Since

P : ∐_{{c′:p(c′)=c_{n}}} Hom(c′_{n−1}, c′) → Hom(c_{n−1}, c_{n})

is a bijection, there is a unique morphism g of 𝒞′ with src(g) = c′_{n−1} sent to f_{n} : c_{n−1} → c_{n}. We define F (f_{1}, …, f_{n}) to be trg(g), and the image of the inclusion of (f_{1}, …, f_{n−1}) in (f_{1}, …, f_{n}) to be g. This actually defines the functor F through level n, since by the induction hypothesis F assigns to the inclusion of any proper substring (f_{1}, …, f_{k}) in (f_{1}, …, f_{n−1}) a morphism h from F (f_{1}, …, f_{k}) to c′_{n−1} in 𝒞′; then F sends the inclusion of (f_{1}, …, f_{k}) in (f_{1}, …, f_{n}) to gh.

Remark. If we think of the functor π : 𝒞̃ → 𝒞 as a function on the object sets, then the number of objects of 𝒞̃ that π sends to p ∈ Ob 𝒞 is u(ˆ0; p) = d(ˆ0; p): this follows from Proposition 2.5.

The construction of 𝒞 in the preceding result is functorial: given a morphism F : 𝒞 → 𝒟 of unilateral updown posets, we have a morphism F̃ : 𝒞̃ → 𝒟̃ given by

F̃(f_{1}, f_{2}, …, f_{n}) = (F (f_{1}), F (f_{2}), …, F (f_{n})).

Also, the updown category 𝒞 is evidently simple. Thus, if 𝔖𝔘 is the full subcategory of simple updown categories in 𝔘, then there is a functor 𝔘𝔘 → 𝔖𝔘 taking 𝒞 to 𝒞̃. In fact, we have the following result.

Proposition 3.4. The functor 𝔘𝔘 → 𝔖𝔘 taking 𝒞 to 𝒞̃ is right adjoint to the inclusion functor 𝔖𝔘 → 𝔘𝔘.

Proof. It suffices to show that

Hom_{𝔘𝔘}(𝒞, 𝒟) ≅ Hom_{𝔖𝔘}(𝒞, 𝒟̃)

for any simple updown category 𝒞 and unilateral updown category 𝒟. A morphism F : 𝒞 → 𝒟 of unilateral updown categories gives rise to F̃ : 𝒞̃ → 𝒟̃, and since 𝒞 is simple there is a natural identification 𝒞 ≅ 𝒞̃, giving us a morphism 𝒞 → 𝒟̃. To go back the other way, just compose with the covering map π : 𝒟̃ → 𝒟.

4 Commutation Conditions

We shall consider various conditions on the commutator of the operators D and U introduced in §2. In what follows we write P_{i} for the restriction of the operator P to level i, so [D, U]_{i} = D_{i+1}U_{i} − U_{i−1}D_{i}.

Definition 4.1. Let 𝒞 be an updown category, with operators D and U as defined above. We write I for the identity operator on 𝕜(Ob 𝒞).

1. If [D, U] = rI, where r is a scalar, then 𝒞 satisfies the absolute commutation condition (ACC) with constant r.

2. If [D, U]_{i} = (ai + b)I_{i} for constants a, b then 𝒞 satisfies the linear commutation condition (LCC) with slope a.

3. If [D, U]_{i} = r_{i}I_{i} for some sequence of scalars {r_{0}, r_{1}, …, }, then 𝒞 satisfies the sequential commutation condition (SCC).

4. If every element of Ob 𝒞 is an eigenvector for [D, U], then 𝒞 satisfies the weak commutation condition (WCC).

Evidently ACC ⟹ LCC ⟹ SCC ⟹ WCC. We can rephrase the preceding definition as follows. The updown category 𝒞 satisfies the WCC if there is a function ϵ : Ob 𝒞 → 𝕜 such that (DU − UD)(c) = ϵ(c)c for all c ∈ Ob 𝒞. Then 𝒞 satisfies the ACC if ϵ(c) is independent of c, the LCC if ϵ(c) is a linear function of |c|, and the SCC if ϵ(c) is an arbitrary function of |c|. We have the following result about products; cf. Lemma 2.2.3 of [2].

Proposition 4.1. Let 𝒞 and 𝒟 be updown categories.

1. If 𝒞 satisfies the ACC with constant r and D satisfies the ACC with constant s, then 𝒞 × 𝒟 satisfies the ACC with constant r + s.

2. If 𝒞 and 𝒟 satisfy the LCC with slope a, then so does 𝒞 × 𝒟.

3. If 𝒞 and 𝒟 satisfy the WCC, then so does 𝒞 × 𝒟.

Proof. Since any element of 𝒞 × 𝒟 covering (c, d) ∈ Ob(𝒞 × 𝒟) must have the form (c′, d) with c′ covering c or (c, d′) with d′ covering d, we have

U(c, d) = ∑_{|c′|=|c|+1} u(c; c′)(c′, d) + ∑_{|d′|=|d|+1} u(d; d′)(c, d′) = (Uc, d) + (c, Ud),

and similarly for D. If 𝒞 and 𝒟 satisfy the WCC, we can calculate that

(DU − UD)(c, d) = ((DU − UD)c, d) + (c, (DU − UD)d) = (ϵ(c) + ϵ(d))(c, d),

from which all three parts follow easily.

The following result generalizes Proposition 2.4 of [4].

Proposition 4.2. Let 𝒞 be an updown category satisfying the WCC, and define ϵ : Ob 𝒞 → 𝕜 as above. Then for objects c_{1}, c_{2} of 𝒞,

⟨U(c_{1}), U(c_{2})⟩ − ⟨D(c_{1}), D(c_{2})⟩ = \begin{cases}0, & if c_{1} ≠ c_{2}; \\ ϵ(c)| Aut(c)|, & if c_{1} = c_{2} = c. \end{cases}

Proof. Calculate using the adjointness of U and D.

Remark. The second alternative of this result can be written

∑_{c′⊳c}u(c; c′)^{2}| Aut(c′)| − ∑_{c′′⊲c}d(c′′; c)^{2}| Aut(c′′)| = ϵ(c)| Aut(c)|,

or, dividing by | Aut(c)| and using equation (1),

∑_{c′⊳c}u(c; c′)d(c; c′) − ∑_{c′′⊲c}u(c′′; c)d(c′′; c) = ϵ(c).  (7)

In an updown category satisfying the SCC, we can obtain the kinds of results proved by Stanley for sequentially differential posets [11] and by Fomin for r-graded graphs in [2]. For example, we have the following result by essentially the same proof as Theorem 2.3 of [11] (see also Proposition 2.7 of [4]).

Proposition 4.3. Let 𝒞 be an updown category satisfying the SCC, and let p ∈ 𝒞_{k}. Call a word w = w_{1}w_{2} ⋯ w_{s} in U and D a valid p-word if the number of U’s minus the number of D’s in w is k, and, for each 1 ≤ i ≤ s, the number of D’s in w_{i} ⋯ w_{s} does not exceed the number of U’s. For such a word w, let S = {i : w_{i} = D} and

c_{i} = |{j : j > i, w_{j} = U}| − |{j : j ≥ i, w_{j} = D}|, i ∈ S.

Then for any valid p-word w,

⟨wˆ0, p⟩ = d(ˆ0; p) ∏_{i∈S}(r_{0} + r_{1} + ⋯ + r_{c_{i}}).

This result has the following corollary (cf. [4, Proposition 2.8] and [2, Theorem 1.5.2]).

Proposition 4.4. Let 𝒞 be an updown category satisfying the SCC, and let p ∈ 𝒞_{k}. Then for nonnegative a,

∑_{|q|=k+a} d(p; q)u(ˆ0; q) = u(ˆ0; p) ∏_{i=0}^{a−1}(r_{0} + r_{1} + ⋯ + r_{k+i}).

Proof. Set w = D^{a}U^{a+k} in the preceding result to get

⟨D^{a}U^{a+k}ˆ0, p⟩ = d(ˆ0; p) ∏_{i=0}^{a−1}(r_{0} + r_{1} + ⋯ + r_{k+i}).

Expand out the left-hand side to get

∑_{|q|=k+a} u(p; q)d(ˆ0; q) = d(ˆ0; p) ∏_{i=0}^{a−1}(r_{0} + r_{1} + ⋯ + r_{k+i}).

Now use equation (1) and divide by | Aut p|/| Aut ˆ0| to obtain the conclusion.

In the case p = ˆ0 the preceding result is

∑_{|q|=a} d(ˆ0; q)u(ˆ0; q) = ∏_{i=0}^{a−1}(r_{0} + r_{1} + ⋯ + r_{i}).  (8)

Comparable results in the case where 𝒞 merely satisfies the WCC appear to be much more complicated. From equation (7) we have

∑_{|q|=1} u(ˆ0; q)d(ˆ0; q) = ϵ(ˆ0),  (9)

generalizing the case a = 1 of equation (8). Since ϵ(ˆ0)ˆ0 = (DU − UD)ˆ0 = DUˆ0, it follows that (DU)^{n}ˆ0 = (ϵ(ˆ0))^{n}ˆ0 for all n. We use this in proving the following result, which generalizes cases a = 2 and a = 3 of equation (8).

Proposition 4.5. If 𝒞 satisfies the WCC, then

∑_{|q|=2} u(ˆ0; q)d(ˆ0; q) = ϵ(ˆ0)^{2} + ∑_{|p|=1} u(ˆ0; p)d(ˆ0; p)ϵ(p)
∑_{|t|=3} u(ˆ0; t)d(ˆ0; t) = ∑_{|p|=1} u(ˆ0; p)d(ˆ0; p)(ϵ(p) + ϵ(ˆ0))^{2} + ∑_{|q|=2} u(ˆ0; q)d(ˆ0; q)ϵ(q).

Proof. For the first part, write D^{2}U^{2} = (DU)^{2} + D[D, U]U and apply it to ˆ0:

⟨D^{2}U^{2}ˆ0, ˆ0⟩ = ⟨(DU)^{2}ˆ0, ˆ0⟩ + ∑_{|p|=1}⟨u(ˆ0, p)D[D, U]p, ˆ0⟩

= (ϵ(ˆ0))^{2}⟨ˆ0, ˆ0⟩ + ∑_{|p|=1}⟨u(ˆ0; p)ϵ(p)Dp, ˆ0⟩

= (ϵ(ˆ0))^{2}| Aut ˆ0| + ∑_{|p|=1} u(ˆ0; p)ϵ(p)d(ˆ0; p)| Aut ˆ0|.

On the other hand,

⟨D^{2}U^{2}ˆ0, ˆ0⟩ = ⟨U^{2}ˆ0, U^{2}ˆ0⟩ = ∑_{|q|=2} ∑_{|p|=2} u(ˆ0; p)u(ˆ0; q)⟨p, q⟩ = ∑_{|q|=2} u(ˆ0; q)^{2}| Aut(q)|

and the first part follows using equation (1).

To prove the second part, start by applying

D^{3}U^{3} = D^{2}[D, U]U^{2} + DUD[D, U]U + D[D, U]^{2}U + D[D, U]UDU + (DU)^{3}

to ˆ0 and proceed similarly, making use of equation (9).

5 Examples

In this section we present ten examples of updown posets. Many of the associated weighted-relation posets appear in the last section of [3]. For the convenience of the reader we have included a cross-reference to [3] at the beginning of each example where it applies. Example 1. Let 𝒞 be an updown category such that 𝒞_{1} consists of a single object ˆ1, 𝒞_{n} = ∅ for n ≠ 0, 1, and Hom(ˆ0, ˆ1) has a single element. The groups Aut(ˆ0) and Aut(ˆ1) are trivial since they act freely on the one-element set Hom(ˆ0, ˆ1). Then

(DU − UD)ˆ0 = Dˆ1 = ˆ0,

and

(DU − UD)ˆ1 = −Uˆ0 = −ˆ1,

so 𝒞 satisfies the LCC with slope −2. Of course 𝒞 is simple. Example 2. (Subsets of a finite set; [3, Example 1]) Let 𝒟 = 𝒞^{n}, where 𝒞 is the updown category of Example 1. There is an identification of objects of 𝒟 with subsets of {1, 2, …, n}: an n-tuple (c_{1}, …, c_{n}) corresponds to the set {i : c_{i} = ˆ1}. The induced partial order is inclusion of sets, and for |p′| = |p| + 1 we have

u(p; p′) = d(p; p′) = \begin{cases}1, & if p is a subset of p′, \\ 0, & otherwise. \end{cases}

The category 𝒟 is unilateral, but not simple for n ≥ 2. In [3] it is shown that the universal cover 𝒟̃ is the simple updown category whose level-m elements are linearly ordered melement subsets of of {1, …, n}, and whose morphisms are inclusions of initial segments. From Proposition 4.1, 𝒟 satisfies the LCC with slope −2; in fact, it is easy to see that (DU − UD)p = (n − 2|p|)p for any object p of 𝒟. Example 3. Let 𝒞 be the category with 𝒞_{n} = {[n]}, where [n] = {1, 2, …, n} (and [0] = ∅), and let Hom([m], [n]) be the set of injective functions from [m] to [n]. Then the axioms are easily seen to hold, with Aut[n] = Σ_{n} (the symmetric group on n letters). Since Hom([n], [n+1]) has (n+1)! elements, we have u([n]; [n+1]) = 1 and d([n]; [n+1]) = n+1. More generally, we have u([n]; [m]) = 1 and d([n]; [m]) = m!/n! for m ≥ n. The unilateral updown poset 𝒞^{↑} is just the infinite chain ℕ regarded as a simple updown category. On the other hand, a morphism of 𝒞^{↓} from [n] to [n + 1] can be thought of as an element of [n + 1] (the element that a representative injective function [n] → [n + 1] misses), and so a level-n object of 𝒞̃^{↓} can be identified with a chain (i_{1}, i_{2}, …, i_{n}) of positive integers with i_{j} ≤ j.

We have U([n]) = [n + 1] and D([n]) = n[n − 1], so

(DU − UD)([n]) = (n + 1)[n] − n[n] = [n],

and thus 𝒞 satisfies the ACC with constant 1. Cf. Example 2.2.1 of [2]. Example 4. (Monomials; [3, Example 2]) Let 𝒟 = 𝒞^{n}, where 𝒞 is the updown category of Example 3. Objects of 𝒟 can be identified with monomials in n commuting indeterminates t_{1}, …, t_{n}. The automorphism group of t_{1}^{i_{1}}t_{2}^{i_{2}} ⋯ t_{n}^{i_{n}} is Σ_{i_{1}} ×Σ_{i_{2}} ×⋯×Σ_{i_{n}}, and a monomial u precedes a monomial v in the induced partial order if u is a factor of v. We have

u(1; t_{1}^{i_{1}} ⋯ t_{n}^{i_{n}}) = \frac{(i_{1} + ⋯ + i_{n})!}{i_{1}! ⋯ i_{n}!} and d(1; t_{1}^{i_{1}} ⋯ t_{n}^{i_{n}}) = (i_{1} + ⋯ + i_{n})!.

The weighted-relation poset W rp(𝒟^{↑}) appears in [3], where it is shown that the universal cover 𝒟̃^{↑} can be identified with the simple updown category whose objects are monomials in n noncommuting indeterminates T_{1}, …, T_{n}, and whose morphisms are inclusions as left factors. From Proposition 4.1, 𝒟 satisfies the ACC with constant n. Cf. Example 2.2.2 of [2].

Example 5. (Necklaces; [3, Example 3]) For a fixed positive integer c, let 𝒩_{m} be the set of m-bead necklaces with beads of c possible colors. More precisely, a level-m object of 𝒩 is an equivalence class of functions f : Z/mZ → [c], where f is equivalent to g if there is some n so that f(a + n) = g(a) for all a ∈ Z/mZ. Thus, for c = 2 the equivalence class

{(1, 1, 2, 2), (2, 1, 1, 2), (2, 2, 1, 1), (1, 2, 2, 1)} represents the necklace .

A morphism from the equivalence class of f in 𝒩_{m} to the equivalence class of g in 𝒩_{n} is an injective function h : Z/mZ → Z/nZ with f(a) = gh(a) for all a ∈ Z/mZ, and such that h preserves the cyclic order, i.e., if we pick representatives of the h(i) in Z with 0 ≤ h(i) ≤ n − 1, then some cyclic permutation of (h(0), h(1), …, h(m − 1)) is an increasing sequence.

In [3] the covering space of the weighted-relation poset W rp(𝒩^{↑}) is constructed as the set of necklaces with labelled beads. It is also shown that for p ∈ 𝒩_{m},

u(ˆ0, p) = \frac{m!}{| Aut(p)|},

so it follows from equation (2) that d(ˆ0, p) = m! for all p ∈ 𝒩_{m}.

If c = 1, then 𝒩_{n} has a single element p_{n}. Evidently U(p_{n}) = np_{n+1} and D(p_{n}) = np_{n−1}, so

(DU − UD)p_{n} = n(n + 1)p_{n} − n^{2}p_{n} = np_{n}

and 𝒩 satisfies the LCC with slope 1. For c ≥ 2, 𝒩 does not satisfy the WCC. For example, when c = 2 we have

(DU − UD)(  ) = 6  + 2  .

Example 6. (Integer partitions with unit weights; [3, Example 5]) Let 𝒴 be the category with Ob 𝒴 the set of integer partitions, i.e., finite sequences (λ_{1}, λ_{2}, …, λ_{k}) of positive integers with

λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k}.

The level of a partition is |λ| = λ_{1} + λ_{2} + ⋯ + λ_{k}; we write ℓ(λ) for the length (number of parts) of λ. The set of morphisms Hom(λ, μ) contains a single element if and only if λ_{i} ≤ μ_{i} for all i. Then 𝒴 is evidently unilateral but not simple. The weights u(λ; μ) = d(λ; μ) appear in the ring of symmetric functions: we have

s_{1}^{k}s_{λ} = ∑_{|μ|=|λ|+k} u(λ; μ)s_{μ}

where s_{μ} is the Schur symmetric function associated with the partition μ (for definitions see [7]). In [3] it is shown that the universal cover 𝒴̃ is the poset of standard Young tableaux, so u(ˆ0; λ) = d(ˆ0; λ) is the number of standard Young tableaux of shape λ.

That 𝒴 satisfies the ACC with constant 1 is shown in [10] (Corollary 1.4), where 𝒴 is the motivating example of theory of differential posets; 𝒴 also appears as Example 1.6.8 of [2].

Example 7. Let 𝒦 be the category with Ob 𝒦 the set of integer partitions, and Hom(λ, μ) defined as follows. Let λ = (λ_{1}, …, λ_{n}) and μ = (μ_{1}, …, μ_{m}), always written in decreasing order. Then a morphism from λ to μ is an injective function f : [n] → [m] such that λ_{i} ≤ μ_{i} whenever f(i) = j.

The partial order induced on Ob 𝒦 = Ob 𝒴 is the same as that of the preceding example: the difference is that we now have nontrivial automorphism groups and weights on covering relations. The automorphism group of λ = (λ_{1}, …, λ_{k}) is the subgroup of Σ_{k} consisting of those permutations σ such that λ_{i} = λ_{j} whenever σ(i) = j. For a partition λ, let m_{k}(λ) be the number of times k occurs in λ. Then for partitions λ, μ with |μ| = |λ|+1, we can describe the weights explicitly as

u(λ; μ) = \begin{cases}1, & if μ is obtained from λ by adding a new part of size 1, \\ m_{k}(λ), & if μ is obtained by increasing a part of size k in λ to k + 1, \\ 0, & otherwise. \end{cases}

d(λ; μ) = \begin{cases}m_{1}(μ), & if μ is obtained from λ by adding a new part of size 1, \\ m_{k+1}(μ), & if μ is obtained increasing a part of size k in λ to size k + 1, \\ 0, & otherwise. \end{cases}

The weights d(λ; μ) appear implicitly in [6] and explicitly in [5], where they are referred to as “Kingman’s branching”: see especially Figure 4 of [5]. As noted there, the d(λ; μ) have an algebraic interpretation similar to that of the last example: in the ring of symmetric functions we have

m_{1}^{k}m_{λ} = ∑_{|μ|=|λ|+k} d(λ; μ)m_{μ},

where m_{λ} is the monomial symmetric function associated with λ.

The universal cover 𝒦̃^{↑} can be described in terms of set partitions: in fact, we can identify elements of 𝒦̃_{n}^{↑} with partitions of [n] so that the covering map π : 𝒦̃^{↑} → 𝒦^{↑} takes a partition P of [n] to the integer partition of n given by the block sizes of P. Actually we will identify elements of 𝒦̃_{n}^{↑} with ordered partitions (P_{1}, …, P_{k}) of [n], where

|P_{1}| ≥ |P_{2}| ≥ ⋯ ≥ |P_{1}|

and, if |P_{i}| = |P_{j}| for i < j, max P_{i} < max P_{j}. We do this by using the construction of Proposition 3.3. Assign the unique partition of [1] to the morphism from ˆ0 to (1), and suppose inductively that we have assigned an ordered partition P = (P_{1}, …, P_{k}) of [n] to the chain (h_{1}, …, h_{n}) of morphisms between adjacent levels of 𝒦^{↑} from ˆ0 to trg(h_{n}) = (λ_{1}, …, λ_{k}) ∈ Ob 𝒦_{n}^{↑} so that λ_{i} = |P_{i}|. Let f ∈ Hom_{𝒦} (λ, μ) be a representative of the equivalence class h_{n+1} ∈ Hom_{𝒦^{↑}} (λ, μ), where |μ| = n+1. If μ has length k+1, there is a unique element i ∈ [k+1] not in the image of f; in this case assign (P_{1}, …, P_{k}, {n+1}) to the chain (h_{1}, …, h_{n}, h_{n+1}). Otherwise, μ has length k and there is a unique i ∈ [k] such that λ_{i} < μ_{f(i)}: in this case, assign to (h_{1}, …, h_{n+1}) the rearrangement of (P′_{1}, …, P′_{k}), where

P′_{j} = \begin{cases}P_{j} ∪ \{n + 1\}, & if j = i, \\ P_{j}, & otherwise, \end{cases}

so that P′_{i} immediately follows P′_{m}, where m = max{j < i : |P′_{j}| ≥ |P′_{i}|}. Evidently the set partition assigned to (h_{1}, …, h_{n+1}) projects to μ in either case.

Level-n objects of the universal cover 𝒦̃^{↓} can be described as sequences s = (a_{1}, …, a_{n}) such that m_{1}(s) ≥ m_{2}(s) ≥ ⋯, where m_{i}(s) is the number of occurrences of i in s; the covering map sends s to (m_{1}(s), m_{2}(s), …). As in the preceding paragraph, we can proceed inductively using the construction of Proposition 3.3. Start by assigning s = (1) to the morphism from ˆ0 to (1). Suppose now we have assigned s = (a_{1}, …, a_{n}) to a chain of morphisms (h_{1}, …, h_{n}) between adjacent levels of 𝒦^{↓} from ˆ0 to λ = (λ_{1}, …, λ_{k}) ∈ 𝒦_{n}^{↓} so that m_{i}(s) = λ_{i} for 1 ≤ i ≤ k, and let h_{n+1} ∈ Hom_{𝒦^{↓}} (λ, μ) where |μ| = n + 1. Now a representative f ∈ Hom_{𝒦} (λ, μ) of h_{n+1} must be “almost an automorphism” exchanging parts of equal size with just one exception: there is a unique i ∈ [ℓ(μ)] such that either i is not in the image of f (in which case μ_{i} = 1), or else λ_{f^{−1}(i)} < μ_{i} (in which case μ_{i} = λ_{f^{−1}(i)} + 1). Let S = {j > i : λ_{f^{−1}(j)} = μ_{i}}: note that S is independent of the choice of f. Now define a permutation σ of [ℓ(μ)] as follows. If S = ∅, let σ be the identity; otherwise, if S = {i + 1, …, l}, let σ(a) = a + 1 for i ≤ a ≤ l − 1, σ(l) = i, and σ(a) = a for a ∉ {i, …, l}. We then assign the sequence s′ = (σ(a_{1}), …, σ(a_{k}), i) to the chain (h_{1}, …, h_{n}, h_{n+1}). If i ∉ im f, then μ_{j} = 1 for j ≥ i and either i = ℓ(μ) = k + 1 (if S is empty) or l = ℓ(μ) = k + 1 (if it isn’t): either way μ differs by λ by having 1 inserted in the ith position, and s′ projects to μ. If μ_{i} = λ_{f^{−1}(i)} + 1, then we must have λ_{j} = μ_{j} for j < i, and μ differs from λ in having a part of size μ_{i} − 1 increased by 1. If S is empty, λ_{f^{−1}(i)} = λ_{i} and μ_{i} = m_{i}(s′) = m_{i}(s) + 1 = λ_{i} + 1. Otherwise, μ_{i} = m_{i}(s′) = m_{l}(s) + 1 = λ_{f^{−1}(l)} and m_{j+1}(s′) = m_{j}(s) for i ≤ j ≤ l − 1. Either way, s′ again projects to μ.

The updown poset 𝒦 satisfies the WCC with ϵ(λ) = 1 + m_{1}(λ). That is,

(DU − UD)(λ) = (1 + m_{1}(λ))λ  (10)

for all partitions λ. To prove this, we introduce the union operation on partitions, e.g., (2, 1) ∪ (3, 1, 1) = (3, 2, 1, 1, 1). If we extend ∪ linearly to 𝕜(Ob 𝒦), then it is straightforward to show that

D(λ ∪ μ) = D(λ) ∪ μ + λ ∪ D(μ)
U(λ ∪ μ) = U(λ) ∪ μ + λ ∪ U(μ) − λ ∪ μ ∪ (1)

for partitions λ, μ. An easy calculation then shows

(DU − UD)(λ ∪ μ) = (DU − UD)(λ) ∪ μ + λ ∪ (DU − UD)(μ) − λ ∪ μ,

and since m_{1}(λ ∪ μ) = m_{1}(λ) + m_{1}(μ), equation (10) must hold for λ ∪ μ whenever it holds for λ and μ. Since (10) is easy to show for partitions with one part, the general result follows by induction on length.

Example 8. (Integer compositions; [3, Example 6]) Let 𝒞_{n} be the set of integer compositions of n, i.e. sequences I = (i_{1}, …, i_{p}) of positive integers with a_{1} + ⋯ + a_{m} = n; as with partitions we write ℓ(I) for the length of I. A morphism from (i_{1}, …, i_{p}) ∈ 𝒞_{n} to (j_{1}, …, j_{q}) ∈ 𝒞_{m} is an order-preserving injective function f : [p] → [q] such that i_{a} ≤ j_{f(a)} for all a ∈ [p]. Then 𝒞 is a unilateral updown category (but not simple). The weights u(I; J) = d(I; J) have an algebraic interpretation similar to that of the preceding two examples, but here one has to use the ring of quasi-symmetric functions (for definitions see [9, Sect. 9.4]): if M_{I} is the monomial quasi-symmetric function associated with I, then

M_{1}^{k}M_{I} = ∑_{|J|=|I|+k} u(I; J)M_{J}.

The universal cover 𝒞̃ is constructed in [3] using Cayley permutations as defined in [8]: a Cayley permutation of level n is a length-n sequence s = (a_{1}, …, a_{n}) of positive integers such that any positive integer i < j appears in s whenever j does. The covering map π : 𝒞̃ → 𝒞 sends a sequence s to the composition (m_{1}(s), m_{2}(s), …). To relate this to the construction of Proposition 3.3, we again proceed inductively. Send the morphism from ˆ0 to (1) to the Cayley permutation (1), and suppose we have assigned to a chain (h_{1}, h_{2}, …, h_{n}) of morphisms between consecutive levels of 𝒞 from ˆ0 to I = (i_{1}, …, i_{k}) ∈ 𝒞_{n} a Cayley permutation s = (a_{1}, …, a_{n}) that projects to I: note that max{a_{1}, …, a_{n}} = k. Now let h_{n+1} ∈ Hom(I, J) with J ∈ 𝒞_{n+1}. Then either ℓ(J) = k and h_{n+1} is the identity function on [k], or ℓ(J) = k + 1. In the first case, there is exactly one position q where J differs from I: assign to (h_{1}, …, h_{n+1}) the Cayley permutation s′ = (a_{1}, …, a_{n}, q). Then m_{q}(s′) = m_{q}(s) + 1 = i_{q} + 1 and m_{i}(s′) = m_{i}(s) for i ≠ q, so s′ projects to J. In the second case, there is exactly one element q ∈ [k + 1] that h_{n+1} misses: assign s′ = (h_{n+1}(a_{1}), …, h_{n+1}(a_{n}), q) to (h_{1}, …, h_{n+1}). Then π(s′) = (m_{1}(s′), m_{2}(s′), …) differs from I only in having an additional 1 inserted in the qth place, and so must be J.

The updown category 𝒞 satisfies the WCC with

ϵ(I) = ℓ(I) + 2m_{1}(I) + 1,  (11)

where m_{1}(I) is the number of 1’s in I. This can be proved by induction on length using a method similar to that used for the preceding example. First, it is easy to show that

(DU − UD)(I) = (2m_{1}(I) + 2)(I)

when ℓ(I) = 1. Now let I ⊔ J be the juxtaposition of compositions I and J, and extend ⊔ linearly to 𝕜(Ob 𝒞). Then

D(I ⊔ J) = D(I) ⊔ J + I ⊔ D(J)
U(I ⊔ J) = U(I) ⊔ J + I ⊔ D(U) − I ⊔ (1) ⊔ J

for compositions I, J. Hence we can calculate that

(DU − UD)(I ⊔ J) = (DU − UD)(I) ⊔ J + I ⊔ (DU − UD)(J) − I ⊔ J.

Since ℓ and m_{1} are additive with respect to the operation ⊔, it follows that I ⊔ J is an eigenvector of DU − DU with eigenvalue given by equation (11) whenever I and J are.

Example 9. (Planar rooted trees; [3, Example 4]) Let 𝒫_{n} consist of functions f : [2n] → {−1, 1} so that the partial sums S_{i} = f(1) + ⋯ + f(i) have the properties that S_{i} ≥ 0 for all 1 ≤ i ≤ 2n, and S_{2n} = 0. We declare Aut(f) to be trivial for all objects f of 𝒫, and define a morphism from f ∈ 𝒫_{n} to g ∈ 𝒫_{n+1} to be an injective, order-preserving function h : [2n] → [2n + 2] such that the two values of [2n + 2] not in the image of h are consecutive, and f(i) = gh(i) for 1 ≤ i ≤ 2n. Then 𝒫 is a unilateral updown category. Using the well-known identification of balanced bracket arrangements with planar rooted trees, e.g.

(1, 1, −1, 1, 1, −1, −1, −1) is identified with ,

we can think of 𝒫 as the updown category of planar rooted trees; the level is the count of non-root vertices.

The weighted-relation poset W rp(𝒫) appears as Example 4 in [3], and its universal cover is described as the poset whose level-n elements are permutations (a_{1}, a_{2}, …, a_{2n}) of the multiset {1, 1, 2, 2, …, n, n} such that, if a_{i} > a_{j} with i < j, then there is some k < j, k ≠ i, such that a_{k} = a_{i}. (The covering map sends a sequence s = (a_{1}, …, a_{2n}) to a sequence of 1’s and −1’s by sending the first occurrence of i in s to 1 and the second to −1.) This construction can be identified with 𝒫̃ as constructed in Proposition 3.3 in an obvious way. For example, consider the morphism from ˆ0 = ∅ to (1, 1, −1, 1, −1, −1) given by the composition h_{3}h_{2}h_{1}, where h_{1} = ∅, h_{2} = {(1, 1), (2, 4)} and h_{3} = {(1, 1), (2, 2), (3, 3), (4, 6)}. We can code the chain (h_{1}, h_{2}, h_{3}) by the sequence (1, 2, 2, 3, 3, 1).

Using the tree language, we can think of U(t) as the sum of all planar rooted trees obtained by attaching a new edge and terminal vertex at every possible position of t (a sum with 2|t| + 1 terms), and D(t) as the sum of all tree obtained by deleting a terminal edge of t. For example,

U(  ) =  +  +  +  +

and

D(  ) =  + .

The updown poset 𝒫 satisfies the WCC with

ϵ(t) = 2|t| + τ(t) + 1,  (12)

where τ(t) is the number of terminal vertices of t. This can be proved by a method similar to that of the preceding two examples, but here we need two operations: a binary operation ∨ and a unary operation B_{+}. The binary operation ∨ : 𝒫_{n} × 𝒫_{m} → 𝒫_{n+m} can be described as juxtaposition of balanced bracket arrangements, or equivalently as joining two planar rooted trees at the root:

∨  =  .

The unary operation B_{+} : 𝒫_{n} → 𝒫_{n+1} encloses a balanced bracket operation in an outer pair of delimiters, or equivalently adds a new root vertex at the top of a planar rooted tree:

B_{+}(  ) =  .

Now it is straightforward to show that

D(t_{1} ∨ t_{2}) = D(t_{1}) ∨ t_{2} + t_{1} ∨ D(t_{2})
U(t_{1} ∨ t_{2}) = U(t_{1}) ∨ t_{2} + t_{1} ∨ U(t_{2}) − t_{1} ∨ ∨t_{2}

for any two planar rooted trees t_{1}, t_{2}, and that

D(B_{+}(t)) = B_{+}(D(t))
U(B_{+}(t)) = B_{+}(U(t)) + ∨ U(t) + U(t) ∨

for any planar rooted tree t. Using the first pair of these equations, we can calculate that

(DU − UD)(t_{1} ∨ t_{2}) = (DU − UD)(t_{1}) ∨ t_{2} + t_{1} ∨ (DU − UD)(t_{2}) − t_{1} ∨ t_{2}

for any planar rooted trees t_{1}, t_{2}: since τ(t_{1} ∨ t_{2}) = τ(t_{1}) + τ(t_{2}), it follows that t_{1} ∨ t_{2} is an eigenvector of DU − UD satisfying equation (12) whenever t_{1} and t_{2} are. Similarly, the second pair of equations gives

(DU − UD)B_{+}(t) = B_{+}((DU − UD)(t)) + 2B_{+}(t)

for any planar rooted tree t. Since τ(B_{+}(t)) = τ(t), it follows that B_{+}(t) is an eigenvector of DU − UD satisfying (12) when t is. Now any planar rooted tree t with |t| > 0 can be written as either t_{1} ∨ t_{2} or B_{+}(t_{1}), so we can prove the result by induction on |t|. Example 10. (Rooted trees; [3, Example 7]) Let 𝒯_{n} consist of partially ordered sets P such that (1) P has n + 1 elements; (2) P has a greatest element; and (3) for any v ∈ P, the set of elements of P exceeding v forms a chain. The Hasse diagram of such a poset P is a tree with the greatest element (the root vertex) at the top. A morphism of 𝒯 from P ∈ 𝒯_{m} to Q ∈ 𝒯_{n} is an injective order-preserving function f : P → Q that sends the root of P to the root of Q, and which preserves covering relations (i.e., if v ⊲ w in the partial order on P, then f(v) ⊲ f(w) in the partial order on Q). Then 𝒯 is an updown category.

The updown category 𝒯 was studied extensively in [4], though without using the categorical language. To see that the construction of the preceding paragraph gives the same multiplicities as in [4], consider a morphism from P ∈ 𝒯_{n} to Q ∈ 𝒯_{n+1}. Any such morphism misses only some terminal vertex v ∈ Q, so we can think of it as identifying P with Q − {v}. Elements of

Hom(P, Q)/ Aut(Q)

amount to different choices for the parent of v in Q, i.e., different choices for terminal vertices of P to which a new edge and vertex can be attached to form Q: this is n(P; Q) as defined in [4]. On the other hand, elements of

Hom(P, Q)/ Aut(P)

amount to different choices of v, and thus to different choices for an edge of Q that when cut leaves P: this is m(P; Q) as defined in [4].

The operators U and D on 𝕜(Ob 𝒯) appear in §2 of [4] as 𝔑 and 𝔓 respectively. As is proved there (Proposition 2.2), 𝒯 satisfies the LCC with ϵ(t) = |t| + 1 (Note that the grading in [4] differs by 1 from the one used here.)

In [3] the weighted-relation poset W rp(𝒯^{↑}) is discussed, and it is shown that the universal cover 𝒯̃^{↑} can be described as permutations of [n]. Finding a simple description of the objects of 𝒯̃^{↓} appears to be a harder problem.

References

[1] S. V. Fomin, The generalized Robinson-Schensted-Knuth correspondence (Russian), Zap. Nauchn. Sem. Leningrad. Otel Mat. Inst. Steklov. (LOMI) 155 (1986), Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII, 156-175; translation in J. Soviet Math. 41 (1988), 979-991.

[2] S. Fomin, Duality of graded graphs, J. Algebraic Combin. 3 (1994), 357-404.

[3] M. E. Hoffman, An analogue of covering space theory for ranked posets, Electron. J. Combin. 8 (2001), res. art. 32.

[4] M. E. Hoffman, Combinatorics of rooted trees and Hopf algebras, Trans. Amer. Math. Soc. 355 (2003), 3795-3811.

[5] S. Kerov, The boundary of Young lattice and random Young tableaux, Formal Power Series and Algebraic Combinatorics (New Brunswick, NJ 1994), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 24, American Mathematical Society, Providence, RI, 1996, pp. 133-158.

[6] J. F. C. Kingman, Random partitions in population genetics, Proc. Roy. Soc. London Ser. A 361 (1978), 1-20.

[7] I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, New York, 1995.

[8] M. Mor and A. S. Fraenkel, Cayley permutations, Disc. Math. 48 (1984), 101-112.

[9] C. Reutenauer, Free Lie Algebras, Oxford University Press, New York, 1993.

[10] R. P. Stanley, Differential posets, J. Amer. Math. Soc. 1 (1988), 919-961.

[11] R. P. Stanley, Variations on differential posets, Invariant Theory and Tableaux (Minneapolis, MN 1988), IMA Volumes in Mathematics and its Applications 19, Springer-Verlag, New York, 1990, pp. 145-165.