See by year See by month Jump to month

Eva Czabarka (University of South Carolina, Columbia): Inducibility in binary trees and tanglegram crossing numbers

 Download as iCal file
Monday, 4. July 2016, 15:30 - 16:30
Abstract. Leaf-labeled binary trees (a.k.a. phylogenetic trees) and tanglegrams are of interest to biologists. For a rooted binary tree on $n$ leaves, any subset of $k$ leaves induces a rooted binary tree by taking all paths connecting these leaves, placing the new root on the vertex closest to the original root of the tree, and suppressing all non-root degree two vertices in the resulting tree. The inducibility of a $k$-leaf rooted binary tree in an $n$-leaf rooted binary tree is the proportion of $k$-subsets of leaves that induce a tree isomorphic to that tree; the inducibility of any rooted binary tree is the limit superior of its
inducibility in any sequence of binary trees. We show a number of results on the inducibility of certain types of binary trees. A tanglegram is a pair of rooted binary trees on the same number of leaves with a fixed matching on the leaves; its crossing number is the minimum number of crossings we can have when we draw this in the plane such that the two binary trees are drawn as plane trees and the crossings are only allowed on the edges corresponding to the given matchings. The tanglegram crossing number is used to
estimate relevant biological quantities (e.g. in parasite-host trees). We show that the
expected value of tangregram crossing number in a random tanglegram on $n$-leaf trees is $\Theta(n^2)$, i.e. as large as possible.
Location : Bolyai Intézet, I. emelet, Riesz terem, Aradi Vértanúk tere 1., Szeged

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013