Planar triangulations, bridgeless planar maps and Tamari intervals

Abstract

We present a direct bijection between planar 3-connected triangulations and bridgeless planar maps, which were first enumerated by Tutte (1962) and Walsh and Lehman (1975) respectively. Previously known bijections by Wormald (1980) and Fusy (2010) are all defined recursively. Our direct bijection passes by a new class of combinatorial objects called "sticky trees". We also present bijections between sticky trees, intervals in the Tamari lattices and closed flows on forests. With our bijections, we recover several known enumerative results about these objects. We thus show that sticky trees can serve as a nexus of bijective links among all these equi-enumerated objects.

23 pages, 11 figures, published

References in corpus (3)

• Sur le nombre d'intervalles dans les treillis de Tamari
• The enumeration of generalized Tamari intervals
• A trinity of duality: non-separable planar maps, $\beta$-(1,0) trees and synchronized intervals

Cited by in corpus (6)

• A partial order on Motzkin paths
• Bijective link between Chapoton's new intervals and bipartite planar maps
• A sequent calculus for the Tamari order
• A sequent calculus for a semi-associative law
• Pattern avoidance in the matching pattern poset
• Bijections between planar maps and planar linear normal $\lambda$-terms with connectivity condition