DMTCS Proceedings, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)

Font Size:  Small  Medium  Large

On a Subposet of the Tamari Lattice

Sebastian A. Csar, Rik Sengupta, Warut Suksompong

Abstract


We discuss some properties of a subposet of the Tamari lattice introduced by Pallo (1986), which we call the comb poset. We show that three binary functions that are not well-behaved in the Tamari lattice are remarkably well-behaved within an interval of the comb poset: rotation distance, meets and joins, and the common parse words function for a pair of trees. We relate this poset to a partial order on the symmetric group studied by Edelman (1989).
Résumé. Nous discutons d'un subposet du treillis de Tamari introduit par Pallo. Nous appellons ce poset le comb poset. Nous montrons que trois fonctions binaires qui ne se comptent pas bien dans le trellis de Tamari se comptent bien dans un intervalle du comb poset : distance dans le trellis de Tamari, le supremum et l'infimum et les parsewords communs. De plus, nous discutons un rapport entre ce poset et un ordre partiel dans le groupe symétrique étudié par Edelman.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional