Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 295 - Mathematics Colloquium

Sergey Kitaev

Strathclyde University

Two involutions on description trees and their applications

Abstract:

Description trees were introduced by Cori, Jacquard and Schaeffer in 1997 to give a general framework for the recursive decompositions of several families of planar maps studied by Tutte in a series of papers in the 1960s. We are interested in two classes of planar maps which can be thought as connected planar graphs embedded in the plane or the sphere with a directed edge distinguished as the root. These classes are rooted non-separable (or, 2-connected) and bicubic planar maps, and the corresponding to them trees are called, respectively, $\beta(1,0)$-trees and $\beta(0,1)$-trees. Using different ways to generate these trees we define two endofunctions on them that turned out to be involutions. These involutions are not only interesting in their own right, in particular, from counting fixed points point of view, but also they were used to obtain non-trivial equidistribution results on planar maps, certain pattern avoiding permutations, and objects counted by the Catalan numbers. The results to be presented in this talk are obtained in a series of papers in collaboration with several researchers.

Host: Jeff Remmel

January 17, 2013

3:00 PM

AP&M 6402

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