Planar triangulations, bridgeless planar maps and Tamari intervals

DOI10.1016/J.EJC.2017.12.002MaRDI QIDQ1746569zbMATH OpenOpenAlexFDO

Authors W. Fang

Publication date 25 April 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Tamari latticesclosed flows on forestssticky trees

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30)

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.

Recommendations

• New bijective links on planar maps via orientations
• New bijective links on planar maps
• Intervals in Catalan lattices and realizers of triangulations

Cites work

• scientific article; zbMATH DE number 3732085 (Why is no real title available?)
• A Census of Planar Triangulations
• A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals
• Counting rooted maps by genus. III: Nonseparable maps
• Higher trivariate diagonal harmonics via generalized Tamari posets
• Intervals in Catalan lattices and realizers of triangulations
• New bijective links on planar maps via orientations
• On the number of intervals in Tamari lattices
• Planar maps
• The enumeration of generalized Tamari intervals
• The enumeration of generalized Tamari intervals
• The number of intervals in the \(m\)-Tamari lattices
• Two bijections on Tamari intervals

Cited in

(13)

• Mating of discrete trees and walks in the quarter-plane
• Some properties of a new partial order on Dyck paths
• Enumerative combinatorics of intervals in the Dyck pattern poset
• A sequent calculus for a semi-associative law
• New bijective links on planar maps
• A partial order on Motzkin paths
• Intervals in the greedy Tamari posets
• Bijections between fighting fish, planar maps, and Tamari intervals
• The combinatorics of a tree-like functional equation for connected chord diagrams
• Bijections between planar maps and planar linear normal \(\lambda\)-terms with connectivity condition
• Geometric realizations of Tamari interval lattices via cubic coordinates
• scientific article; zbMATH DE number 7204452 (Why is no real title available?)
• Enumeration of some classes of pattern avoiding matchings, with a glimpse into the matching pattern poset

This page was built for publication: Planar triangulations, bridgeless planar maps and Tamari intervals

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