Untangling the parabola: two problems in double coset enumeration

Matjaž Konvalinka
FMF, University of Ljubljana

PDF

Minisymposium: COMBINATORICS

Content: In this talk, I will present two recent results on the enumeration of double cosets in the symmetric group. \emph{Tanglegrams} are a special class of graphs appearing in applications concerning cospeciation and coevolution in biology and computer science. They are formed by identifying the leaves of two rooted binary trees, and can be viewed as a double coset of the symmetric group with respect to the action of the groups of symmetries of the two trees. We give an explicit formula for the number of distinct (asymmetric) binary rooted tanglegrams with $n$ matched vertices, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. A \emph{parabolic double coset} of the symmetric group is a double coset with respect to the action of two parabolic subgroups (one on each side). I will present a formula for enumerating all parabolic double cosets with a given minimal element, along with extensions to arbitrary Coxeter groups and a conjectured asymptotic formula for the total number of parabolic double cosets.

Back to all abstracts