Mireille Bousquet-Mélou ; Guillaume Chapuy ; Louis-François Préville-Ratelle - 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)Article

Authors: Mireille Bousquet-Mélou ORCID1; Guillaume Chapuy 2; Louis-François Préville-Ratelle 3

  • 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 Tn(m), which generalizes the usual Tamari lattice Tn 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 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 Tn(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 Tn(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)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 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.


Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 306 times.
This article's PDF has been downloaded 330 times.