Toward the enumeration of maximal chains in the Tamari lattices

The Tamari lattices have been intensely studied since they first appeared in Dov Tamari’s thesis around 1952. He defined the n-th Tamari lattice T(n) on bracketings of a set of n+1 objects, with a cover relation based on the associativity rule in one direction. Despite their interesting aspects and the attention they have received, a formula for the number of maximal chains in the Tamari lattices is still unknown. The purpose of this thesis is to convey my results on progress toward the solution of this problem and to discuss future work.

A few years ago, Bergeron and Préville-Ratelle generalized the Tamari lattices to the m-Tamari lattices. The original Tamari lattices T(n) are the case m=1. I establish a bijection between maximum length chains in the m-Tamari lattices and standard m-shifted Young tableaux. Using Thrall’s formula, I thus derive the formula for the number of maximum length chains in T(n).

For each i greater or equal to -1 and for all n greater or equal to 1, I define C(i,n) to be the set of maximal chains of length n+i in T(n). I establish several properties of maximal chains (treated as tableaux) and identify a particularly special property: each maximal chain may or may not possess a plus-full-set. I show, surprisingly, that for all n greater or equal to 2i+4, each member of C(i,n) contains a plus-full-set. Utilizing this fact and a collection of maps, I obtain a recursion for the number of elements in C(i,n) and an explicit formula based on predetermined initial values. The formula is a polynomial in n of degree 3i+3. For example, the number of maximal chains of length n in T(n) is n choose 3.

I discuss current work and future plans involving certain equivalence classes of maximal chains in the Tamari lattices. If a maximal chain may be obtained from another by swapping a pair of consecutive edges with another pair in the Hasse diagram, the two maximal chains are said to differ by a square move. Two maximal chains are said to be in the same equivalence class if one may be obtained from the other by making a set of square moves.