Restricted rooted non-separable planar maps
Christopher Severs · arXiv (Cornell University) · 2012
AbstractTutte founded the theory of enumeration of planar maps in a series of papersin the 1960s. Rooted non-separable planar maps have connections, for example,to pattern-avoiding permutations, and they are in one-to-one correspondence withthe β(1,0)-trees introduced by Cori, Jacquard and Schaeffer in 1997. In this paperwe enumerate 2-face-free rooted non-separable planar maps and obtain restrictionson β(1,0)-trees giving k-face-free rooted non-separable planar maps. Moreover, wediscussmultiple-edge-free rooted non-separable planar mapsand provide some roughlower boundsfor their number using restricted β(1,0)-trees. We enumerate so-calledprimitive rooted non-separable planar maps (which form a basis for generating allrooted non-separable planar maps). Finally, we discuss some equinumerous objectssuch as primitive β(1,0)-trees and certain pattern-avoiding permutations. 1 Introduction A map is a partition of a compact oriented surface into three finite sets: a set of vertices (points), a set of