Intervals of balanced binary trees in the Tamari lattice

DOI10.1016/J.TCS.2011.11.020MaRDI QIDQ764359zbMATH OpenOpenAlexFDO

Authors Samuele Giraudo

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.3472

zbMATH Keywords

balanced binary treefixed-point functional equationgenerating seriesgrammarposetTamari lattice

Mathematics Subject Classification ID

Trees (05C05) Combinatorics of partially ordered sets (06A07) Data structures (68P05) Searching and sorting (68P10)

Abstract: We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals [T, T'] where T and T' are balanced binary trees are isomorphic as posets to a hypercube. We introduce synchronous grammars that allow to generate tree-like structures and obtain fixed-point functional equations to enumerate these. We also introduce imbalance tree patterns and show that they can be used to describe some sets of balanced binary trees that play a particular role in the Tamari lattice. Finally, we investigate other families of binary trees that are also closed by interval in the Tamari lattice.

Recommendations

• Balanced binary trees in the Tamari lattice
• On k-dimensional balanced binary trees.
• Balanced partitions of trees and applications
• Balanced partitions of trees and applications
• Bounds on the Balaban index of trees
• On the number of intervals in Tamari lattices
• Tight bounds on the algebraic connectivity of a balanced binary tree
• scientific article; zbMATH DE number 5606397
• Spanning Balanced Trees in Boolean Cubes
• On balance index sets of rooted trees

Cites work

• Algebraic and combinatorial structures on Baxter permutations
• Analytic combinatorics
• Balanced binary trees in the Tamari lattice
• Hopf algebra of the planar binary trees
• scientific article; zbMATH DE number 4075068 (Why is no real title available?)
• scientific article; zbMATH DE number 3178652 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 3108822 (Why is no real title available?)
• Intervals in Catalan lattices and realizers of triangulations
• Order structure on the algebra of permutations and of planar binary trees
• Periodic oscillations of coefficients of power series that satisfy functional equations
• Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law
• The algebra of binary search trees
• The On-Line Encyclopedia of Integer Sequences

Cited in

(4)

• Colored operads, series on colored operads, and combinatorial generating systems
• A Motzkin filter in the Tamari lattice
• Interval decomposition lattices are balanced
• Balanced binary trees in the Tamari lattice

Describes a project that uses

Uses Software

• SageMath
• OEIS

This page was built for publication: Intervals of balanced binary trees in the Tamari lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764359)