Planar triangulations, bridgeless planar maps and Tamari intervals

DOI10.1016/J.EJC.2017.12.002zbMATH Open1384.05072arXiv1611.07922OpenAlexW2549866415MaRDI QIDQ1746569FDOQ1746569

Authors: W. Fang 

Publication date: 25 April 2018

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

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.

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

Recommendations

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

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)

Cites Work

• Planar maps
• A Census of Planar Triangulations
• Counting rooted maps by genus. III: Nonseparable maps
• Higher trivariate diagonal harmonics via generalized Tamari posets
• The number of intervals in the \(m\)-Tamari lattices
• Intervals in Catalan lattices and realizers of triangulations
• On the number of intervals in Tamari lattices
• Two bijections on Tamari intervals
• The enumeration of generalized Tamari intervals
• New bijective links on planar maps via orientations
• Title not available (Why is that?)
• A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals
• The enumeration of generalized 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
• A sequent calculus for a semi-associative law
• Enumerative combinatorics of intervals in the Dyck pattern poset
• 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
• Title not available (Why is that?)
• 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)