combinatorics

On Agreement Subtrees in Multiple Phylogenetic Trees

arXiv:2607.12778

summary

The paper establishes new combinatorial bounds for the number of leaves required so that any k unrooted binary phylogenetic trees always share a common induced subtree, giving a four‑times iterated exponential upper bound and an exponential lower bound.

Abstract

Snir and Yuster [Discrete Appl. Math. 347 (2026) 160--171] asked for the least number such that unrooted binary phylogenetic trees on the same leaves always share a common quartet. We give a new upper bound for the -tree version of the Maximum Agreement Subtree problem, namely an upper bound for the number of leaves, on which unrooted binary phylogenetic trees always share a common induced binary subtree on leaves, which is a four-times iterated exponential function. For , this implies a four-times iterated exponential upper bound. We also set an exponential lower bound for .

Topics & keywords

#phylogenetic trees#agreement subtree#maximum agreement subtree#combinatorial bounds#unrooted binary trees#iterated exponentialunrooted binary phylogenetic treequartetmaximum agreement subtreeiterated exponential boundupper boundlower bound
On Agreement Subtrees in Multiple Phylogenetic Trees · wovepaper