When Many Trees Go to War
Mathias Weller, Norbert Zeh · 2025
Read When Many Trees Go to War by Mathias Weller, Norbert Zeh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-21749.txt.
Introduction
Mathias Weller and Norbert Zeh ask how much extra wiring a network needs to hold many family trees at once in a 2025 paper. In evolution studies, a network can display several trees by adding reticulations, cross-links between branches. Shared structure lets trees share parts of the network.
They show that some sets of trees share almost no usable structure. For a modest number of trees, any network displaying them needs nearly the naive maximum of cross-links. For more trees, the needed count matches the known ceiling for displaying all trees, up to constant factors. Simple counting arguments drive the proofs, which extend to unrooted networks as well.
Catalog record
| CREATOR | Mathias Weller, Norbert Zeh |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-21749
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Many Trees Go to War Mathias Weller, Norbert Zeh Abstract It is known that any two trees on the same n n leaves can be displayed by a network with n − 2 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 t trees on n n leaves, there is a trivial network with ( t − 1 ) n (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 ∈ o ( log n ) t\in o\left(\sqrt{\log n}\right) , there is a set of t t trees with virtually no common structure that could be exploited. More precisely, we show for any t ∈ o ( log n ) t\in o\left(\sqrt{\log n}\right) , there are t t trees such that any network displaying them has ( t − 1 ) n − o ( n ) (t-1)n-o(n) reticulations. For t ∈ o ( log n ) t\in o(\log n) , we obtain a slightly weaker bound. We also prove that already for t = c log n t=c\log n , for any constant c > 0 c>0 , there is a set of t t trees that cannot be displayed by a network with o ( n log n ) o(n\log n) reticulations, matching up to constant factors the known upper bound of O ( n log n ) O(n\log n) reticulations sufficient to display all trees with n n leaves. These results are based on simple counting arguments and extend to unrooted networks and trees. 1 Introduction Phylogenetics is the study of evolutionary relationships among a set of taxa, typically represented using tree-like structures that depict patterns of descent from common ancestors. Traditionally, these relationships have been modelled with phylogenetic trees, which are rooted or unrooted trees whose leaves correspond to present-day taxa and whose internal nodes represent ancestral lineages [ 20 ] . However, due to processes such as hybridization, horizontal gene transfer, and recombination, tree models often fail to capture the full complexity of evolutionary histories [ 10 , 18 , 9 , 1 ] . This has led to the development of phylogenetic networks, which are graphical models that generalize trees by allowing for “reticulate” (non-tree-like) events [ 13 , 19 ] . Both rooted and unrooted versions of trees and networks are considered in practice, depending on the data and the biological questions at hand. Rooted structures incorporate ancestral/temporal directionality, which is important for inferring evolutionary pathways, while unrooted structures are often used when such directionality is unknown or when analyzing symmetric distance data [ 21 , 14 ] . A central concept in the analysis of phylogenetic networks is that of a network “displaying” a tree: informally, a network displays a tree if the tree can be embedded in the network in a way that respects its topology [ 13 ] . A formal definition will be given in section 2 . This notion is at the heart of computational problems in phylogenetics like comparing phylogenies or parsimoniously reconstructing networks [ 6 ] . Indeed, the computational problems Tree Containment (decide whether a given tree is embeddable into a given network) [ 15 , 22 , 8 , 12 , 11 , 26 ] and Hybridization Number (construct a smallest network displaying all given trees) [ 3 , 2 , 7 , 25 , 16 ] have been studied extensively. There is a trivial network that displays any set of t trees without exploiting any common structure (see fig. 1 ). This network is obtained by simply 1. taking the disjoint union of the t trees, 2. adding a tree “cap” that joins the roots of the trees under a common root and, finally, 3. adding reticulations to “merge” all copies of each leaf in the different trees. This network has (t-1)n reticulations and conveys absolutely no information about the similaries between the t trees. In general, this is far from the minimum number of reticulations necessary to display a set of trees: if multiple input trees share subtrees with the same topology, then these subtrees can be embedded into the same part of the network, which may allow us to save reticulations. An interesting question then is whether there exist sets of trees with little enough common structure to make the trivial network essentially the best possible. \Citet BSS05 answered this question in the affirmative for t=2 , by showing that there are two n -caterpillars requiring n-2 reticulations. Recently, [ 24 ] proved that even displaying 3 caterpillars without restrictions on the type of network may require (\nicefrac{{3}}{{2}}-o(1))n reticulations. This left open the possibility that the number of reticulations required to display t trees depends sublinearly on t , and they explicity pose the general case of t trees as an open question. This paper settles this question by showing that the dependence on t is linear after all. Another known special case is t=(2n-3)!! , that is, how many reticulations are necessary to display all trees on the same n leaves? \Citet BS18 showed that this number is in \Theta(n\log n) even for tree-based networks, but the \Omega(n\log n) lower bound is derived via a simple counting argument applied to any type of network. In this paper, we generalize this counting argument to the case of t trees. We show that for t\in o(\log n) , there is a set of t trees for which the trivial network (see Figure 1 ) is asymptotically optimal, in the sense that there are t trees that cannot be displayed by a network with fewer than (t-1)n-o(tn) reticulations. For t\in o\left(\sqrt{\log n}\right) , we obtain the slightly stronger result that there are t trees that cannot be displayed by a network with fewer than (t-1)n-o(n) reticulations. Thus, we conclude that the trivial network is indeed asymptotically optimal in the worst case for displaying t trees. The proof of these two results also shows that, for any constant c>0 , there is a set of c\log n trees that cannot be displayed by a network with o(n\log n) reticulations. One way to interpret this result is that “most” of the reticulations in the \Theta(n\log n) -reticulation network of [ 5 ] that displays all trees on n leaves are caused by a small subset of only O(\log n) trees, and adding the remaining exponentially many trees increases the number of reticulations necessary to display these trees by only a constant factor. As the results by [ 5 , 24 , 3 ] show, the question of how many reticulations are necessary to display a set of t trees has been the focus of previous work and is interesting in its own right. Our interest in this question stems from its connection to cluster reduction. Cluster reduction is a technique that has been verified experimentally