A Characterization of Level- k k Realizability for Clustering Systems
Shilong Dai, Yangjing Long · 2026
Read A Characterization of Level- k k Realizability for Clustering Systems by Shilong Dai, Yangjing Long (2026) 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-2605-21945.txt.
Introduction
Shilong Dai and Yangjing Long ask how much reticulation complexity is forced by data summarized as hardwired clusters. Reticulate events like recombination, hybridization, and horizontal transfer can leave a tree model inadequate for such data. For any cluster system on a finite taxon set, they compute the minimum level of a rooted network whose hardwired clusters match the data. The proof gives a cluster-side criterion, turning a network-design problem into a clear complexity score, distinct from softwired representation where a cluster need only appear in one displayed tree.
Catalog record
| CREATOR | Shilong Dai, Yangjing Long |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92968 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.21945
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Characterization of Level- k k Realizability for Clustering Systems Shilong Dai, Yangjing Long Abstract Rooted phylogenetic networks model evolutionary histories in which tree-like descent is supplemented by reticulate events. A basic invariant of such a network is its hardwired clustering system, consisting of the descendant leaf sets of all vertices. We give a complete Hasse-diagram characterization of when a clustering system 𝒞 \mathcal{C} on a finite taxa set X X is the hardwired clustering system of a rooted level- k k network. For each non-trivial block B B of the Hasse diagram ℋ [ 𝒞 ] \mathcal{H}[\mathcal{C}] , we introduce a parameter μ ( B ) \mu(B) , defined as the minimum size of a generating set for all overlap-intersections in B B . Our main theorem states that a level- k k realization exists if and only if μ ( B ) ≤ k \mu(B)\leq k for every non-trivial block B B . The necessity direction shows that overlap-intersections force proper hybrid vertices in any realizing block. The sufficiency direction is constructive: starting from the Hasse diagram, we iteratively split redundant hybrid vertices, preserving the hardwired clustering system while reducing each block to the required level. Mathematics Subject Classification (2020)]05C20, 05C40, 05C75, 92D15 keywords phylogenetic network, clustering system, hardwired cluster, level- k network, Hasse diagram, reticulation pacs [ 1 Introduction Rooted phylogenetic networks provide a way to represent evolutionary histories in which tree-like descent is supplemented by reticulate events such as hybridization, recombination, or horizontal transfer; see, for example, HusonRuppScornavacca2011 ; HusonScornavacca2011 . One basic object associated with a rooted network N is its hardwired clustering system C_{N} , the family of all sets of descendant leaves of vertices of N . For rooted phylogenetic trees, the corresponding cluster hierarchy determines the tree uniquely SempleSteel2003 . For rooted networks, this uniqueness fails in general NakhlehWang2005 , but the hardwired cluster set still records substantial structural information. Bounded-level networks are a standard way to control the complexity of reticulation: the level bounds, block by block, how many hybrid vertices may occur in a single non-tree-like region. This gives a useful middle ground between trees and unrestricted networks. In this setting, a level bound formalizes the biological assumption that reticulate events are locally limited, even when the whole evolutionary history is not tree-like. Related algorithmic work controls reticulation complexity through decompositions or explicit constructions GusfieldBansalBafnaSong2007 ; WangGuoLiuEtAl2013 , and many bounded-level results start from explicit network encodings such as triplets, trees, or clusters ToHabib2009 ; vanIerselKelkRuppHuson2010 ; GambetteHuber2012 . Hardwired cluster realizability is subtler than the corresponding tree case, and also less direct than many triplet- or split-based settings: a hardwired cluster set records descendant leaf sets, but not the local ancestry by which those sets are produced. In particular, Hasse-hybrid vertices may be redundant, while overlap-intersections of clusters can force hybrid vertices in every realization. Several nearby lines of work address different aspects of this landscape. Cluster networks give a canonical way to summarize a set of clusters HusonRupp2008 , but they are not intended as a criterion for whether the same cluster set has a realization of prescribed level. The constructions of van Iersel et al. focus on representing conflicting clusters with fewer reticulations vanIerselKelkRuppHuson2010 , while Gambette and Huber study encodings of bounded-level networks GambetteHuber2012 . These results show how bounded reticulation complexity can be represented or achieved by explicit constructions. They do not give a necessary-and-sufficient level- k cluster-realization test expressed solely in the Hasse diagram of an arbitrary clustering system. Results on regular networks and related network classes give uniqueness or reconstruction statements within restricted classes BaroniSempleSteel2005 ; Willson2010 ; Zhang2019 ; they likewise do not provide the block-wise hardwired level criterion considered here. This leads to the realizability problem considered in this paper: given a clustering system \mathcal{C} on a finite taxa set X , when does there exist a rooted level- k network N on X with C_{N}=\mathcal{C} ? Our goal is to answer this question directly from the clustering system itself, without first constructing or guessing a realizing network. The Hasse diagram \mathcal{H}[\mathcal{C}] of a clustering system is a natural starting point for this problem. The closest predecessor of our work is the study of clustering systems of phylogenetic networks by Hellmuth, Schaller, and Stadler HellmuthSchallerStadler2023 . Their results show how structural properties of networks are reflected in the induced clustering systems, compare several well-studied classes of phylogenetic networks through their clusters, and provide block and overlap tools that we use. However, their results do not give a blockwise numerical invariant whose value is exactly the minimum level required for realizing a given clustering system. The parameter \mu(B) introduced here fills this gap. More recently, Shanavas, Changat, Hellmuth, and Stadler studied the connections between clustering systems and unique least common ancestors in directed acyclic graphs, relating several classes of set systems to LCA-type properties ShanavasChangatHellmuthStadler2024 . Related developments in the I -LCA framework further investigate how DAGs can be transformed while preserving relevant cluster/LCA structure HellmuthLindeberg2026 . These works are orthogonal to the present paper: they focus on LCA properties and induced set-system axioms, whereas we focus on exact hardwired realization under a level bound. Thus, although existing results provide important structural insight, they do not give, in the general setting considered here, a directly checkable block-wise criterion for when \mathcal{C} is realizable by a rooted level- k network. In other words, one would like to replace the network-side condition “each non-trivial block has at most k proper hybrid vertices” by a condition that can be read directly from \mathcal{H}[\mathcal{C}] . The main contribution of this paper is a purely Hasse-theoretic criterion. For every non-trivial block B of H=\mathcal{H}[\mathcal{C}] , we define a parameter \mu(B) using generating sets for intersections of overlapping clusters inside B . Intuitively, \mu(B) measures the minimum number of independent overlap-intersection regions that any realizing network block must encode. Our main theorem states that \mathcal{C} is realizable by a rooted level- k network if and only if \mu(B)\leq k for every non-trivial block B of \mathcal{H}[\mathcal{C}] . Thus the obstruction to level- k realizability is purely Hasse-theoretic. The necessity direction shows that these overlap-intersection pieces force at least \mu(B) proper hybrid vertices in any corresponding realizing block. The sufficiency direction is constructive: in contrast to the existence and correspondence results above, it gives an explicit procedure that transforms the Hasse diagram into a level- k realization without changing the hardwired clustering system. Figure 1 summarizes this route from the input clustering system to the level criterion. Proof strategy. The proof separates the two directions of the characterization. For necessity, we show that every overlap-intersection inside a non-trivial Hasse block must be represented, in any realizing network, by descendant clusters of proper hybrid vertices in a corresponding network block. This gives the lower bound \mu(B)\leq h(B_{N}) . For sufficiency, we start from the Hasse diagram and iteratively split all redundant hybrid vertices. The split operation preserves the hardwired clustering system, while a lexicographic descent argument shows that the process terminates. In the final network, each block has at most \mu(B) proper hybrid vertices. Clustering system \mathcal{C} Hasse diagram H=\mathcal{H}[\mathcal{C}] Non-trivial blocks B Overlap-intersections \mathcal{I}(B) Generating sets