On Agreement Subtrees in Multiple Pylogenetic Trees

Snir and Yuster [Discrete Appl.

Math.

347 (2026) 160--171] asked for the least number $h(k)$ such that $k$ unrooted binary phylogenetic trees on the same $h(k)$ leaves always share a common quartet.

We give a new upper bound for the $k$-tree version of the Maximum Agreement Subtree problem, namely an upper bound for the number of leaves, on which $k$ unrooted binary phylogenetic trees always share a common induced binary subtree on $n$ leaves, which is a four-times iterated exponential function.

For $h(k)$, this implies a four-times iterated exponential upper bound.

We also set an exponential lower bound for $h(k)$.