When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure
Discrete Mathematics & Theoretical Computer Science · 10.03.2026 · vol. 28:2 (Combinatorics)
DOI: 10.46298/dmtcs.16446 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 10.03.2026. Verfasst von Mathias Weller und 1 weiteren Autor:innen.
Abstract (Originalsprache)
It is known that any two trees on the same $n$ leaves can be displayed by a network with $n-2$ reticulations, and there are two trees that cannot be displayed by a network with fewer reticulations. But how many reticulations are needed to display multiple trees? For any set of $t$ trees on $n$ leaves, there is a trivial network with $(t - 1)n$ reticulations that displays them. To do better, we have to exploit common structure of the trees to embed non-trivial subtrees of different trees into the same part of the network. In this paper, we show that for $t \in o(\sqrt{\lg n})$, there is a set of $t$ trees with virtually no common structure that could be exploited. More precisely, we show for any $t\in o(\sqrt{\lg n})$, there are $t$ trees such that any network displaying them has $(t-1)n - o(n)$ reticulations. For $t \in o(\lg n)$, we obtain a slightly weaker bound. We also prove that already for $t = c\lg n$, for any constant $c > 0$, there is a set of $t$ trees that cannot be displayed by a network with $o(n \lg n)$ reticulations, matching up to constant factors the known upper bound of $O(n \lg n)$ reticulations sufficient to display \emph{all} trees with $n$ leaves. These results are based on simple counting arguments and extend to unrooted networks and trees.
Zitieren
APA
Weller, M., & Zeh, N. (2026). When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Combinatorics). https://doi.org/10.46298/dmtcs.16446
Vancouver
Weller M, Zeh N. When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Combinatorics). doi:10.46298/dmtcs.16446
BibTeX
@article{Weller2026,
author = {Weller, Mathias and Zeh, Norbert},
title = {When Many Trees Go to War: On Sets of Phylogenetic Trees With Almost No Common Structure},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2026},
volume = {vol. 28:2},
number = {Combinatorics},
doi = {10.46298/dmtcs.16446}
}
EUVIMED