Restricted non-separable planar maps and some pattern avoiding permutations

DOI10.1016/J.DAM.2013.01.004MaRDI QIDQ2444543zbMATH OpenOpenAlexFDO

Authors Sergey Kitaev, Pavel Salimov, Christopher Severs, Henning Úlfarsson

Publication date 10 April 2014

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

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

zbMATH Keywords

description treepermutation patternplanar map

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Trees (05C05)

Abstract: Tutte founded the theory of enumeration of planar maps in a series of papers in the 1960s. Rooted non-separable planar maps are in bijection with West-2-stack-sortable permutations, beta(1,0)-trees introduced by Cori, Jacquard and Schaeffer in 1997, as well as a family of permutations defined by the avoidance of two four letter patterns. In this paper we give upper and lower bounds on the number of multiple-edge-free rooted non-separable planar maps. We also use the bijection between rooted non-separable planar maps and a certain class of permutations, found by Claesson, Kitaev and Steingrimsson in 2009, to show that the number of 2-faces (excluding the root-face) in a map equals the number of occurrences of a certain mesh pattern in the permutations. We further show that this number is also the number of nodes in the corresponding beta(1,0)-tree that are single children with maximum label. Finally, we give asymptotics for some of our enumerative results.

Recommendations

• Permutations with forbidden subsequences and nonseparable planar maps
• Enumeration of rooted vertex non-separable planar maps
• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
• Enumeration of permutations with restricted subsequences
• A bijective census of nonseparable planar maps

Cites work

• A Census of Planar Maps
• A combinatorial proof of J. West's conjecture
• A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
• An involution on bicubic maps and \beta(0,1)-trees
• Analytic combinatorics
• Baxter permutations and plane bipolar orientations
• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
• Description trees and Tutte formulas.
• Enumerating \((2 + 2)\)-free posets by indistinguishable elements
• Enumeration of Non-Separable Planar Maps
• Generalized permutation patterns and a classification of the Mahonian statistics
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• On the Asymptotic Number of Plane Curves and Alternating Knots
• Patterns in permutations and words.
• Permutations with forbidden subsequences and nonseparable planar maps
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations

Cited in

(7)

• Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
• A combinatorial proof of J. West's conjecture
• Permutations with forbidden subsequences and nonseparable planar maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• The skew Brownian permuton: A new universality class for random constrained permutations
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Enumeration of fixed points of an involution on \(\beta(1,0)\)-trees

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Restricted non-separable planar maps and some pattern avoiding permutations

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