The enumeration of generalized Tamari intervals

• Published in: Transactions of the American Mathematical Society 2017-07, Vol.369 (7), p.5219-5239
• Main Authors: Préville-Ratelle, Louis-François, Viennot, Xavier
• Format: Article
• Language: English
• Subjects: Combinatorics; Mathematics; Research article
• ISSN: 0002-9947; 1088-6850
• DOI: 10.1090/tran/7004

For any finite path vv on the square grid consisting of north and east unit steps, starting at (0,0), we construct a poset Tam(v)(v) that consists of all the paths weakly above vv with the same number of north and east steps as vv. For particular choices of vv, we recover the traditional Tamari lattice and the mm-Tamari lattice. Let v←\overleftarrow {v} be the path obtained from vv by reading the unit steps of vv in reverse order, replacing the east steps by north steps and vice versa. We show that the poset Tam(v)(v) is isomorphic to the dual of the poset Tam(v←)(\overleftarrow {v}). We do so by showing bijectively that the poset Tam(v)(v) is isomorphic to the poset based on rotation of full binary trees with the fixed canopy vv, from which the duality follows easily. This also shows that Tam(v)(v) is a lattice for any path vv. We also obtain as a corollary of this bijection that the usual Tamari lattice, based on Dyck paths of height nn, can be partitioned into the (smaller) lattices Tam(v)(v), where the vv are all the paths on the square grid that consist of n−1n-1 unit steps. We explain possible connections between the poset Tam(v)(v) and (the combinatorics of) the generalized diagonal coinvariant spaces of the symmetric group.