Two involutions on description trees and their applications
Sergey Kitaev · 2013
Description trees were introduced by Cori, Jacquard and Schaeer 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, (1; 0)-trees and (0; 1)-trees. Using dierent ways to generate these trees we dene two endofunctions on them that turned out to be involutions. These involutions are not only interesting in their own right, in particular, from counting xed 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.