Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 269 - Combinatorics

Sergey Kitaev

Reykjavik University; University of Strathclyde

Planar maps and description trees

Abstract:

Tutte founded the enumeration theory of planar maps in a series of papers in the 1960s. We are interested in rooted planar maps which can be thought as connected planar graphs embedded in the sphere with a directed edge distinguished as the root. A planar map is non-separable if it has no loops and no cut-vertices. Non-separable planar maps are also called 2-connected maps. Another class of maps of our interest is bicubic maps, which after removing the root orientation are connected regular bipartite graphs with vertex degree 3. Cori, Jacquard and Schaeffer introduced description trees in 1997, to give a general framework for the recursive decompositions of several families of planar maps studied by Tutte. These trees are not only interesting in their own right, but also they proved to be a useful tool in obtaining non-trivial equidistribution results on planar maps, certain pattern avoiding permutations, and objects counted by Catalan numbers. In this talk, I will provide an overview of several recent results and research trends related to planar maps and description trees. Most of the results are ``work in progress'' of several research teams.

February 15, 2011

3:00 PM

AP&M 7321

****************************