6533b7cefe1ef96bd1257aab
RESEARCH PRODUCT
A Motzkin filter in the Tamari lattice
Jean-luc BarilJean Marcel Pallosubject
Discrete mathematicsMathematics::CombinatoricsBinary tree010102 general mathematicsLattice (group)0102 computer and information sciences[ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]01 natural sciencesUpper and lower boundsTheoretical Computer ScienceCombinatoricsJoin and meet010201 computation theory & mathematics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Discrete Mathematics and CombinatoricsOrder (group theory)Ideal (order theory)0101 mathematicsFilter (mathematics)Tamari latticeComputingMilieux_MISCELLANEOUSMathematicsdescription
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distance between two Motzkin trees in T n which gives the exact value for some specific pairs of Motzkin trees.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-03-18 |