A trinity of duality: non-separable planar maps, (1,0)-trees and synchronized intervals

DOI10.1016/J.AAM.2017.10.001MaRDI QIDQ1693341zbMATH OpenOpenAlexFDO

Authors W. Fang

Publication date 31 January 2018

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(\beta-(1,0)\) treesbijectionmap dualitynon-separable planar mapsrecursive decompositionsynchronized intervals

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Trees (05C05) Enumeration in graph theory (05C30)

Abstract: The dual of a map is a fundamental construction on combinatorial maps, but many other combinatorial objects also possess their notion of duality. For instance, the Tamari lattice is isomorphic to its order dual, which induces an involution on the set of so-called "synchronized intervals" introduced by Pr'eville-Ratelle and the present author. Another example is the class of $$-(1,0) trees, which has a mysterious involution $h$ proposed by Claesson, Kitaev and Steingr'imsson (2009). These two classes of combinatorial objects are all in bijection with the class of non-separable planar maps, which is closed by map duality. In this article, we show that we can identify the notions of duality in these three classes of objects using previously known natural bijections, which leads to a bijective proof of a result from Kitaev and de Mier (2013). We also discuss how various statistics are transferred by duality and by the bijections we used.

Recommendations

• Enumeration of fixed points of an involution on \(\beta(1,0)\)-trees
• From generalized Tamari intervals to non-separable planar maps (extended abstract)
• Non-crossing trees, quadrangular dissections, ternary trees, and duality-preserving bijections
• An involution on bicubic maps and \beta(0,1)-trees
• Left ternary trees and non-separable rooted planar maps

Cites work

• A bijective census of nonseparable planar maps
• A Census of Planar Maps
• An involution on \(\beta (1,0)\)-trees
• Counting smaller trees in the Tamari order
• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
• Description trees and Tutte formulas.
• Enumeration of fixed points of an involution on \(\beta(1,0)\)-trees
• Intervals in Catalan lattices and realizers of triangulations
• On the number of intervals in Tamari lattices
• On the number of self-dual rooted maps
• Patterns in permutations and words.
• Permutations with forbidden subsequences and nonseparable planar maps
• The enumeration of generalized Tamari intervals
• The enumeration of generalized Tamari intervals
• Two bijections on Tamari intervals

Cited in

(12)

• Planar triangulations, bridgeless planar maps and Tamari intervals
• Some properties of a new partial order on Dyck paths
• Non-crossing trees, quadrangular dissections, ternary trees, and duality-preserving bijections
• A partial order on Motzkin paths
• The rise-contact involution on Tamari intervals
• Fighting fish and two-stack sortable permutations
• A bijection between Tamari intervals and extended fighting fish
• Bijections for generalized Tamari intervals via orientations
• Intervals in the greedy Tamari posets
• The ascent lattice on Dyck paths
• A bijection between non-separable planar maps and fighting fish
• Enumeration of fixed points of an involution on \(\beta(1,0)\)-trees

This page was built for publication: A trinity of duality: non-separable planar maps, \(\beta(1,0)\)-trees and synchronized intervals

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