Proceedings of the 28-th International Conference on Formal Power Series and Algebraic Combinatorics
4-8 Jul 2016 Vancouver, British Columbia (Canada)

Extended abstracts listed by author > Matsen Iv Frderick

Monday 4
Combinatorics
Karen Yeats
› 17:30 - 19:00 (1h30)
› SFU Harbour Center - Segal Centre Conference Rooms 1400 - 1410
On trees, tanglegrams, and tangled chains
Sara Billey  1  , Matjaz Konvalinka  2  , Frderick Matsen Iv  3  
1 : Department of Mathematics, University of Washington, USA
2 : Department of Mathematics, University of Ljubljana & Institute for Mathematics, Physics and Mechanics
Ljubljana -  Slovénie
3 : Computational Biology Program, Fred Hutchinson Cancer Research Center
Seattle, WA 98109 -  États-Unis

Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with n leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared. 



  • Poster
Online user: 1