Mireille BousquetMélou ; Guillaume Chapuy ; LouisFrançois PrévilleRatelle

The representation of the symmetric group on $m$Tamari intervals (conference version)
dmtcs:3045 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

https://doi.org/10.46298/dmtcs.3045
The representation of the symmetric group on $m$Tamari intervals (conference version)
1 Laboratoire Bordelais de Recherche en Informatique
2 Laboratoire d'informatique Algorithmique : Fondements et Applications
3 Laboratoire de combinatoire et d'informatique mathématique [Montréal]
An $m$ballot path of size $n$ is a path on the square grid consisting of north and east unit steps, starting at (0,0), ending at $(mn,n)$, and never going below the line $\{x=my\}$. The set of these paths can be equipped with a lattice structure, called the $m$Tamari lattice and denoted by $\mathcal{T}{_n}^{(m)}$, which generalizes the usual Tamari lattice $\mathcal{T}n$ obtained when $m=1$. This lattice was introduced by F. Bergeron in connection with the study of diagonally coinvariant spaces in three sets of $n$ variables. The representation of the symmetric group $\mathfrak{S}_n$ on these spaces is conjectured to be closely related to the natural representation of $\mathfrak{S}_n$ on (labelled) intervals of the $m$Tamari lattice studied in this paper. An interval $[P,Q$] of $\mathcal{T}{_n}^{(m)}$ is labelled if the north steps of $Q$ are labelled from 1 to $n$ in such a way the labels increase along any sequence of consecutive north steps. The symmetric group $\mathfrak{S}_n$ acts on labelled intervals of $\mathcal{T}{_n}^{(m)}$by permutation of the labels. We prove an explicit formula, conjectured by F. Bergeron and the third author, for the character of the associated representation of $\mathfrak{S}_n$. In particular, the dimension of the representation, that is, the number of labelled $m$Tamari intervals of size $n$, is found to be $(m+1)^n(mn+1)^{n2}$. These results are new, even when $m=1$. The form of these numbers suggests a connection with parking functions, but our proof is not bijective. The starting point is a recursive description of $m$Tamari intervals. It yields an equation for an associated generating function, which is a refined version of the Frobenius series of the representation. The form of this equation is highly nonstandard: it involves two additional variables $x$ and $y$, a derivative with respect to $y$ and iterated divided differences with respect to $x$. The hardest part of the proof consists in solving it, and we develop original techniques to do so.