Universal rooted phylogenetic tree shapes and universal tanglegrams

2023/08/12 by Clifton, Ann, Czabarka, Eva, Liu, Kevin +4
#05C05 #05C35 #05C60 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2308.06580

Abstract

We provide an Ω(nlog n) lower bound and an O(n²) upper bound for the smallest size of rooted binary trees (a.k.a. phylogenetic tree shapes), which are universal for rooted binary trees with n leaves, i.e., contain all of them as induced binary subtrees. We explicitly compute the smallest universal trees for n≤ 11. We also provide an Ω(n²) lower bound and an O(n⁴) upper bound for the smallest size of tanglegrams, which are universal for size n tanglegrams, i.e., which contain all of them as induced subtanglegrams. Some of our results generalize to rooted d-ary trees and to d-ary tanglegrams.

Related

• Decks of rooted binary trees
• On symmetries in phylogenetic trees
• Tanglegrams: a reduction tool for mathematical phylogenetics
• Counting tanglegrams with species
• Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability