The representation of the symmetric group on m-Tamari intervals
Mireille Bousquet-Mélou, Guillaume Chapuy, Louis-François Préville-Ratelle
Abstract
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 T(m), which generalizes
the usual Tamari lattice T 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 Sn on these spaces is conjectured to be
closely related to the natural representation of Sn on (labelled)
intervals of the m-Tamari lattice studied in
this paper. An interval [P,Q] of T(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 Sn acts on labelled
intervals of T(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 Sn. 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)n-2. 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 non-standard: 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.
Résumé. Un chemin de m-Dyck de taille n est un chemin sur la grille carrée, formé de pas nord et est, qui commence en (0,0), finit en (mn,n), et ne passe jamais sous la droite {x=my}. L'ensemble de ces chemins peut être équipé d'une structure de treillis, appelé treillis de m-Tamari et noté T(m), qui généralise le treillis de Tamari classique, obtenu pour m=1. Ce treillis a été introduit par F. Bergeron en lien avec les espaces coinvariants diagonaux en trois jeux de n variables. On conjecture que l'action de Sn sur ces espaces est reliée à la représentation naturelle de Sn sur les intervalles (étiquetés) du treillis de m-Tamari, action que nous étudions ici. Un intervalle [P,Q] de T(m) est dit étiqueté si les pas nord de Q sont étiquetés de 1 à n de façon à croître le long de chaque suite de pas nord. Le groupe symétrique Sn agit sur les intervalles étiquetés de T(m) en permutant les étiquettes. Nous démontrons une formule explicite, conjecturée par F. Bergeron et le troisième auteur, pour le caractère de cette représentation de Sn. En particulier, la dimension de cette représentation, c'est-à-dire le nombre d'intervalles de m-Tamari étiquetés de taille n, est (m+1)n(mn+1)n-2. Ces résultats sont nouveaux, y compris pour m=1. Leur forme suggère un lien avec les fonctions de stationnement, mais notre preuve n'est pas bijective. Le point de départ est une description récursive des intervalles. Elle mène à une équation pour une série génératrice associée, qui raffine la série de Frobenius de la représentation. Cette équation est d'une forme très inhabituelle : elle fait intervenir deux variables supplémentaires x et y, une dérivée par rapport à y et des différences divisées itérées par rapport à x. La partie la plus difficile de la preuve est la solution de cette équation, et nous développons une technique originale pour y parvenir.
Résumé. Un chemin de m-Dyck de taille n est un chemin sur la grille carrée, formé de pas nord et est, qui commence en (0,0), finit en (mn,n), et ne passe jamais sous la droite {x=my}. L'ensemble de ces chemins peut être équipé d'une structure de treillis, appelé treillis de m-Tamari et noté T(m), qui généralise le treillis de Tamari classique, obtenu pour m=1. Ce treillis a été introduit par F. Bergeron en lien avec les espaces coinvariants diagonaux en trois jeux de n variables. On conjecture que l'action de Sn sur ces espaces est reliée à la représentation naturelle de Sn sur les intervalles (étiquetés) du treillis de m-Tamari, action que nous étudions ici. Un intervalle [P,Q] de T(m) est dit étiqueté si les pas nord de Q sont étiquetés de 1 à n de façon à croître le long de chaque suite de pas nord. Le groupe symétrique Sn agit sur les intervalles étiquetés de T(m) en permutant les étiquettes. Nous démontrons une formule explicite, conjecturée par F. Bergeron et le troisième auteur, pour le caractère de cette représentation de Sn. En particulier, la dimension de cette représentation, c'est-à-dire le nombre d'intervalles de m-Tamari étiquetés de taille n, est (m+1)n(mn+1)n-2. Ces résultats sont nouveaux, y compris pour m=1. Leur forme suggère un lien avec les fonctions de stationnement, mais notre preuve n'est pas bijective. Le point de départ est une description récursive des intervalles. Elle mène à une équation pour une série génératrice associée, qui raffine la série de Frobenius de la représentation. Cette équation est d'une forme très inhabituelle : elle fait intervenir deux variables supplémentaires x et y, une dérivée par rapport à y et des différences divisées itérées par rapport à x. La partie la plus difficile de la preuve est la solution de cette équation, et nous développons une technique originale pour y parvenir.
Full Text: PostScript PDF