Picture of smart phone in human hand

World leading smartphone and mobile technology research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by Strathclyde researchers from the Department of Computer & Information Sciences involved in researching exciting new applications for mobile and smartphone technology. But the transformative application of mobile technologies is also the focus of research within disciplines as diverse as Electronic & Electrical Engineering, Marketing, Human Resource Management and Biomedical Enginering, among others.

Explore Strathclyde's Open Access research on smartphone technology now...

Restricted non-separable planar maps and some pattern avoiding permutations

Kitaev, Sergey and Salimov, Pavel and Severs, Christopher and Ulfarsson, Henning (2013) Restricted non-separable planar maps and some pattern avoiding permutations. Discrete Applied Mathematics, 161 (16-17). pp. 2514-2526. ISSN 0166-218X

Full text not available in this repository. Request a copy from the Strathclyde author

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.