Restricted non-separable planar maps and some pattern avoiding permutations

Sergey Kitaev, Pavel Salimov, Christopher Severs, Henning Ulfarsson

Research output: Contribution to journalArticle

1 Citation (Scopus)

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-22-stack-sortable permutations, β(1,0)β(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 study how certain structures in planar maps transfer to trees and permutations via the bijections. More precisely, we show that the number of 22-faces in a map equals the number of nodes in the corresponding β(1,0)β(1,0)-tree that are single children with maximum label; 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 Steingrímsson in 2009, to show that 22-face-free maps correspond to permutations avoiding certain mesh patterns. Finally, we give asymptotics for some of our enumerative results.
Original languageEnglish
Pages (from-to)2514-2526
Number of pages13
JournalDiscrete Applied Mathematics
Volume161
Issue number16-17
DOIs
Publication statusPublished - Nov 2013

Fingerprint

Pattern-avoiding Permutation
Planar Maps
Nonseparable
Permutation
Bijection
Face
Enumeration
Upper and Lower Bounds
Mesh
Labels
Series
Vertex of a graph

Keywords

  • planar map
  • description trees
  • permutation patterns

Cite this

Kitaev, Sergey ; Salimov, Pavel ; Severs, Christopher ; Ulfarsson, Henning. / Restricted non-separable planar maps and some pattern avoiding permutations. In: Discrete Applied Mathematics. 2013 ; Vol. 161, No. 16-17. pp. 2514-2526.
@article{dd882b7a21ca4a6daa7a0d887be5630d,
title = "Restricted non-separable planar maps and some pattern avoiding permutations",
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-22-stack-sortable permutations, β(1,0)β(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 study how certain structures in planar maps transfer to trees and permutations via the bijections. More precisely, we show that the number of 22-faces in a map equals the number of nodes in the corresponding β(1,0)β(1,0)-tree that are single children with maximum label; 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 Steingr{\'i}msson in 2009, to show that 22-face-free maps correspond to permutations avoiding certain mesh patterns. Finally, we give asymptotics for some of our enumerative results.",
keywords = "planar map, description trees, permutation patterns",
author = "Sergey Kitaev and Pavel Salimov and Christopher Severs and Henning Ulfarsson",
year = "2013",
month = "11",
doi = "10.1016/j.dam.2013.01.004",
language = "English",
volume = "161",
pages = "2514--2526",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
number = "16-17",

}

Restricted non-separable planar maps and some pattern avoiding permutations. / Kitaev, Sergey; Salimov, Pavel; Severs, Christopher; Ulfarsson, Henning.

In: Discrete Applied Mathematics, Vol. 161, No. 16-17, 11.2013, p. 2514-2526.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Restricted non-separable planar maps and some pattern avoiding permutations

AU - Kitaev, Sergey

AU - Salimov, Pavel

AU - Severs, Christopher

AU - Ulfarsson, Henning

PY - 2013/11

Y1 - 2013/11

N2 - 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-22-stack-sortable permutations, β(1,0)β(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 study how certain structures in planar maps transfer to trees and permutations via the bijections. More precisely, we show that the number of 22-faces in a map equals the number of nodes in the corresponding β(1,0)β(1,0)-tree that are single children with maximum label; 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 Steingrímsson in 2009, to show that 22-face-free maps correspond to permutations avoiding certain mesh patterns. Finally, we give asymptotics for some of our enumerative results.

AB - 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-22-stack-sortable permutations, β(1,0)β(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 study how certain structures in planar maps transfer to trees and permutations via the bijections. More precisely, we show that the number of 22-faces in a map equals the number of nodes in the corresponding β(1,0)β(1,0)-tree that are single children with maximum label; 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 Steingrímsson in 2009, to show that 22-face-free maps correspond to permutations avoiding certain mesh patterns. Finally, we give asymptotics for some of our enumerative results.

KW - planar map

KW - description trees

KW - permutation patterns

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/planarMaps.pdf

U2 - 10.1016/j.dam.2013.01.004

DO - 10.1016/j.dam.2013.01.004

M3 - Article

VL - 161

SP - 2514

EP - 2526

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 16-17

ER -