Sebastian A. Csar ; Rik Sengupta ; Warut Suksompong - On a Subposet of the Tamari Lattice

dmtcs:3063 - 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.3063
On a Subposet of the Tamari LatticeConference paper

Authors: Sebastian A. Csar 1; Rik Sengupta 2; Warut Suksompong 3

  • 1 School of Mathematics
  • 2 Department of Mathematics - Princeton University
  • 3 Department of Mathematics [MIT]

[en]
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).

[fr]
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.


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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] poset, Tamari lattice, tree rotation
Funding:
    Source : OpenAIRE Graph
  • Reflection Group Combinatorics; Funder: National Science Foundation; Code: 1001933

2 Documents citing this article

Consultation statistics

This page has been seen 360 times.
This article's PDF has been downloaded 544 times.