Préville-Ratelle, Louis-François and Viennot, Xavier - An extension of Tamari lattices

dmtcs:2535 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
An extension of Tamari lattices

Authors: Préville-Ratelle, Louis-François and Viennot, Xavier

For any finite path $v$ on the square lattice consisting of north and east unit steps, we construct a poset Tam$(v)$ that consists of all the paths lying weakly above $v$ with the same endpoints as $v$. For particular choices of $v$, we recover the traditional Tamari lattice and the $m$-Tamari lattice. In particular this solves the problem of extending the $m$-Tamari lattice to any pair $(a; b)$ of relatively prime numbers in the context of the so-called rational Catalan combinatorics.For that purpose we introduce the notion of canopy of a binary tree and explicit a bijection between pairs $(u; v)$ of paths in Tam$(v)$ and binary trees with canopy $v$. Let $(\overleftarrow{v})$ be the path obtained from $v$ by reading the unit steps of $v$ in reverse order and exchanging east and north steps. We show that the poset Tam$(v)$ is isomorphic to the dual of the poset Tam$(\overleftarrow{v})$ and that Tam$(v)$ is isomorphic to the set of binary trees having the canopy $v$, which is an interval of the ordinary Tamari lattice. Thus the usual Tamari lattice is partitioned into (smaller) lattices Tam$(v)$, where the $v$’s are all the paths of length $n-1$ on the square lattice.We explain possible connections between the poset Tam$(v)$ and (the combinatorics of) the generalized diagonal coinvariant spaces of the symmetric group.


Source : oai:HAL:hal-01337833v1
Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Submitted on: November 21, 2016
Keywords: Tamari lattice,$m$-Tamari lattice,rational Catalan combinatorics,diagonal coinvariant spaces,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 44 times.
This article's PDF has been downloaded 102 times.