6
$\begingroup$

Many of the zillions of combinatorial objects counted by Catalan numbers come with various lattice structures.

The $n$th Tamari lattice $T_n$, as originally defined, is the lattice of all those maps $f:\{1,...,n\}\to\{1,...,n\}$ which satisfy the conditions

  • $i\leqslant f(i)$;

  • if $i\leqslant j\leqslant f(i)$ then $f(j)\leqslant f(i)$,

for all $i,j\in\{1,...,n\}$, ordered valuewise, i. e. by declaring $f\leqslant g$ iff $f(i)\leqslant g(i)$ for all $i\in\{1,...,n\}$. The Hasse diagram of $T_n$ is the edge graph of the $n+1$st associahedron, tilted in a certain tricky way. Here is $T_4$ for example:

T4

(I have omitted the last numbers of node labels, they are all $4$.)

The lattice $D_n$ of all inflationary order preserving maps $f:\{1,...,n\}\to\{1,...,n\}$, that is, maps satisfying

  • $i\leqslant f(i)$;

  • if $i\leqslant j\leqslant f(i)$ then $f(i)\leqslant f(j)$,

again ordered valuewise, has the same number of elements as $T_n$ but looks entirely different. For example, it is always distributive, while $T_n$ is not even modular for $n>2$. Here is the Hasse diagram of $D_4$:

D4

(Last numbers are again omitted, by the same reason.)

Question: is there any natural (e. g. functorial) mapping from finite lattices to finite lattices which carries $T_n$ to $D_n$, or vice versa?

Some remarks which might or might not be relevant.

Intersection of $T_n$ and $D_n$ is the lattice of all closure operators on $\{1,...,n\}$, i. e. order preserving maps $f$ with $i\leqslant f(i)=f(f(i))$. It has $2^{n-1}$ elements and is isomorphic to the powerset of $\{1,...,n-1\}$: to a closure operator $f$ corresponds the subset of strictly $f$-increasing elements, i. e. $\{i\mid f(i)>i\}$, while to a subset $S$ corresponds the operator $f_S$ given by $f_S(i)=\min\{j\mid i\leqslant j\notin S\}$.

On the other hand, both $T_n$ and $D_n$ are embedded in the lattice $I_n$ of all inflationary operators, that is, maps $f$ with $i\leqslant f(i)$ for all $i$ - $D_n$ as a sublattice but $T_n$ only as a meet-subsemilattice. $I_n$ is distributive, it has $n!$ elements and is isomorphic to the lattice product $$ (1<2<3<\dots<n)\times(2<3<\dots<n)\times\cdots\times(n-1<n) $$ of linear orders. It is thus also natural to ask whether there is an operation that transforms the lattice $P_n$ of permutations of $\{1,...,n\}$ under the weak order into $I_n$. Like $T_n$, $P_n$ is not modular for $n>2$. Note that the Hasse diagram of $P_n$ is the edge graph of a permutohedron.

$\endgroup$
16
  • 1
    $\begingroup$ I can make some partial progress. There is a standard bijection between permutations and Lehmer codes en.wikipedia.org/wiki/Lehmer_code . A Lehmer code is a map $g : [n] \to \mathbb{Z}$ with $0 \leq g(i) \leq n-i$; if $g$ is a Lehmer code then $f(i) := i+g(i)$ is an inflationary map. So that gives a bijection between $I_n$ and $S_n$. I believe that, under your definitions, $T_n$ corresponds to 312 avoiding permutations and $D_n$ corresponds to 231 avoiding permutations. These are easy to biject with each other -- just conjugate by $w_0$. $\endgroup$ Commented Oct 10 at 16:27
  • 1
    $\begingroup$ PS $D_n$ is also the lattice of partitions sitting inside the staircase $(n-1, n-2, \dots, 2,1)$, ordered by reverse containment. $\endgroup$ Commented Oct 10 at 17:03
  • 1
    $\begingroup$ FWIW, the distributive lattice of partitions inside a staircase shape is sometimes called the “Stanley lattice.” And there is also a 3rd important lattice on Catalan objects, namely the lattice of noncrosssing set partitions (first studied by Kreweras). I think there are papers studying lattices “between” these three, but I don’t know if any of them address your particular question. $\endgroup$ Commented Oct 10 at 17:55
  • 3
    $\begingroup$ The lattice $D_n$ is also known as the lattice of Dyck paths. It is isomorphic to the lattice of congruences of the Tamari lattice. Even if it is not written explicitly, this can be found in the article On Tamari lattices of Geyer. One can also perfom a strange deformation of the Tamari lattice and find the lattice of Dyck path. This is explained in the article Linear Intervals in the Tamari and the Dyck Lattices and in the alt-Tamari Posets by Chenevière. $\endgroup$ Commented Oct 10 at 18:15
  • 1
    $\begingroup$ Yes exactly, I like to see these new posets as intermediate deformations between the Tamari lattice and the lattice of Dyck path. Of course this is very specific to this example. $\endgroup$ Commented Oct 11 at 13:12

0

You must log in to answer this question.

Browse other questions tagged .