Restricted non-separable planar maps and some pattern avoiding permutations
Discrete Applied Mathematics, Volume 161, Issues 16–17, (2013), Pages 2514-2526
Sergey, Pavel, Christopher and Henning
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.
@article{kitaev2013maps,
author = {Kitaev, Sergey and Salimov, Pavel and Severs, Christopher and Ulfarsson, Henning},
title = {Restricted non-separable planar maps and some pattern avoiding permutations},
journal = {Discrete Applied Mathematics},
volume = {161},
number = {16-17},
pages = {2514--2526},
year = {2013},
doi = {10.1016/j.dam.2013.01.004},
}
Download the paper
Presentations
- Kort, tré og mynstur, Conference of the Icelandic Mathematics Society 2011 (Henning presented)
- Restricted rooted non-separable planar maps, Joint Mathematics Meetings, Boston, MA, January 2012 (Henning presented)
- Crazy bijections between planar maps, beta-trees and perms, ICE-TCS seminar, Reykjavik University, March 2013 (Henning presented)
Later work (last updated 3 October 2026)
- S. Kitaev and A. de Mier, Enumeration of fixed points of an involution on \(\beta(1,0)\)-trees, Graphs Combin. (2014). Counts the fixed points of an involution on the \(\beta(1,0)\)-trees that describe rooted non-separable planar maps.
- All citing papers on Google Scholar (4)