IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Is the induced subtanglegram relation a well quasi order?

  • Dec. 4, 2020
  • 2:30 p.m.

Abstract

A tanglegram of size $n$ is an ordered pair of rooted binary trees, each with $n$ leaves, along with a perfect matching between the leaves. The object comes from bioinformatics, where it is used to model co-speciation and co-evolution. The primary invariant of concern in this talk is the so-called tangle crossing number, that is, the minimum number of unordered crossing edge-pairs over all layouts of the tanglegram. The interest is partially motivated by ease of visualization of the underlying biological processes, and the fact that biologists believe that the tangle crossing number correlates with quantities of interest such as the number of times a parasite switched host or the number of horizontal gene transfers. We define a partial order on the collection of all tanglegrams via the induced subtanglegram relation and state a Kuratowski-like theorem that characterizes tangle-planar tanglegrams. In the spirit of extending this result, the remainder of the talk will be dedicated to determining whether or not the described partial order is well-quasi-ordered.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC