Intervals of balanced binary trees in the Tamari lattice

DOI10.1016/J.TCS.2011.11.020zbMATH Open1277.68065arXiv1107.3472OpenAlexW2028442244MaRDI QIDQ764359FDOQ764359

Authors: Samuele Giraudo 

Publication date: 13 March 2012

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

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.

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

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
• Spanning Balanced Trees in Boolean Cubes
• On balance index sets of rooted trees

zbMATH Keywords

grammarposetTamari latticegenerating seriesbalanced binary treefixed-point functional equation

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

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

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)