Minimum Network Level Forced by Hardwired Cluster Data

Reticulate evolutionary events, such as hybridization, recombination, and horizontal transfer, can make a tree model inadequate.

When evolutionary data are summarized as hardwired clusters, one can ask how much local reticulation complexity is forced by the data itself.

We address this question for an arbitrary cluster system $\mathcal C$ on a finite taxon set $X$ by computing the minimum level of a rooted phylogenetic network whose hardwired cluster system is exactly $\mathcal C$.

Writing $H=\mathcal H[\mathcal C]$, we define for each non-trivial block $B$ of $H$ a parameter $\mu(B)$ from generating sets of incompatibility intersections in $B$.

If $\ell(\mathcal C)$ denotes the minimum level of any rooted network $N$ with $C_N=\mathcal C$, then \[ \ell(\mathcal C)=\max\{\,\mu(B)\mid B\text{ is a non-trivial block of }H\,\}. \] Equivalently, $\mathcal C$ is realizable by a rooted level-$k$ network if and only if $\mu(B)\le k$ for every non-trivial block $B$ of $H$.

The lower-bound proof relates incompatibility intersections to non-root hybrid vertices in realizing blocks, while the upper-bound proof starts from the Hasse diagram and iteratively splits selected hybrid vertices without changing the hardwired cluster system.

The result turns a network-design problem into a cluster-side criterion and provides an interpretable complexity score for hardwired cluster data, distinct from softwired cluster representation where clusters need only occur in one displayed tree.