A Characterization of Level-k Realizability for Clustering Systems

Shilong Dai; Yangjing Long

arxiv: 2605.21945 · v1 · pith:CCVACGVXnew · submitted 2026-05-21 · 🧬 q-bio.MN

A Characterization of Level-k Realizability for Clustering Systems

Shilong Dai , Yangjing Long This is my paper

Pith reviewed 2026-05-22 02:41 UTC · model grok-4.3

classification 🧬 q-bio.MN

keywords clustering systemslevel-k networksrooted phylogenetic networksHasse diagramoverlap intersectionshybrid verticesrealizabilitytaxa clustering

0 comments

The pith

A clustering system on taxa is the hardwired clustering system of a rooted level-k network if and only if μ(B) ≤ k for every non-trivial block B of its Hasse diagram.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper gives an exact if-and-only-if test for when a clustering system on a finite set of taxa equals the hardwired clusters of some rooted level-k network. It works by building the Hasse diagram H of the clustering system, identifying its non-trivial blocks, and defining for each block B a number μ(B) that equals the size of the smallest family of clusters whose overlaps generate every intersection piece inside that block. The theorem states that a realizing level-k network exists precisely when μ(B) never exceeds k. A reader would care because the test converts an existence question about networks into a finite check on the diagram, and the proof supplies an explicit construction that starts from the diagram and produces the network. If the claim holds, the minimum level needed for any given clustering system is simply the largest μ(B) across its blocks.

Core claim

The paper proves that there exists a rooted level-k network N with C_N = C if and only if μ(B) ≤ k for every non-trivial block B of H = H[C]. The necessity direction shows that each overlap-intersection piece inside a block must be realized by a distinct non-root hybrid vertex. The sufficiency direction supplies a constructive algorithm that begins with the Hasse diagram, repeatedly splits chosen hybrid vertices while preserving the hardwired clustering system, and stops with a network whose level is bounded by the block-wise values of μ.

What carries the argument

The parameter μ(B), defined for each non-trivial block B of the Hasse diagram H of the clustering system as the size of the smallest family of clusters that together generate all overlap-intersection pieces inside B.

If this is right

If μ(B) ≤ k holds for every block, the iterative splitting procedure produces an explicit rooted level-k network whose hardwired clustering system equals C.
The smallest k for which a given clustering system is level-k realizable equals the maximum of μ(B) over all non-trivial blocks.
Any network realizing C must contain at least μ(B) non-root hybrid vertices inside the subgraph corresponding to each block B.
The characterization turns the search for a realizing network into a per-block combinatorial minimization problem on the overlap intersections.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The constructive sufficiency proof may be turned into an algorithm that both decides realizability and outputs a realizing network of controlled level.
The block-wise bound on level suggests that global network properties such as total reticulation number can sometimes be read off directly from local overlap data in the Hasse diagram.
The same style of argument might apply to other bounded-reticulation classes once an analogous minimum-family parameter is identified for their defining constraints.

Load-bearing premise

The necessity direction assumes that every overlap-intersection piece inside a block must be represented by a non-root hybrid vertex in any realizing network.

What would settle it

A clustering system containing one block B with μ(B) = k+1 for which a level-k network nevertheless realizes all of C would falsify the necessity claim.

read the original abstract

We give a Hasse-diagram characterization of when a clustering system $\mathcal C$ on a finite taxa set $X$ is the hardwired clustering system $C_N$ of a rooted level-$k$ network. For each non-trivial block $B$ of $H=\mathcal H[\mathcal C]$, we define a parameter $\mu(B)$ using minimum families of clusters that generate all overlap-intersections inside $B$. The main theorem proves that there exists a rooted level-$k$ network $N$ with $C_N=\mathcal C$ if and only if $\mu(B)\le k$ for every non-trivial block $B$ of $H$. The necessity proof shows that overlap-intersection pieces must be represented by non-root hybrid vertices in any realizing block. The sufficiency proof is constructive: starting from the Hasse diagram, it iteratively splits selected hybrid vertices, preserves the hardwired clustering system, and terminates with a realization whose level is bounded by the block-wise values of $\mu$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a direct iff characterization of level-k realizability for clustering systems via the block-wise minimum-family parameter μ on the Hasse diagram.

read the letter

The main takeaway is that a clustering system C is the hardwired clustering system of some rooted level-k network exactly when μ(B) ≤ k for every non-trivial block B in the Hasse diagram H of C, where μ(B) is the size of the smallest family generating the overlap-intersections inside that block. This is the clean new piece: an exact local condition on blocks rather than a global search over networks. The necessity argument shows that each overlap-intersection piece inside a block must be realized by a distinct non-root hybrid vertex, which directly sets the lower bound on level. The sufficiency side is constructive, starting from the Hasse diagram and iteratively splitting hybrids while preserving the exact clusters and capping the level at the maximum μ value. That constructive route is the practical strength here, because it turns the characterization into something that could guide an algorithm for building the network when the condition holds. The parameter μ is computed straight from the input clusters via minimum generating families, so there is no circularity in the criterion. The math stays within standard phylogenetic network machinery and the citation pattern looks appropriate for the area. On the soft side, the necessity step rests on the claim that no root placement or single shared hybrid can cover multiple overlap pieces without raising the level. If a realizing network could encode some intersections more efficiently through shared structure, then μ would overestimate the required level and the iff would fail. The abstract indicates the authors rule this out by how hybrids are represented in the block, but the construction details would need checking to confirm it never introduces extra reticulations. Minor concern only, since the outline is consistent. This is for researchers in computational phylogenetics who work on cluster-based network reconstruction or reticulation bounds. A reader who needs an exact test for level-k realizability will get direct value from the block-wise condition. It deserves a serious referee because the central claim is specific, the proofs are outlined without obvious gaps, and the result could support further algorithmic work. I would send it to peer review.

Referee Report

1 major / 1 minor

Summary. The manuscript claims to characterize exactly when a clustering system C on a finite taxa set X is the hardwired clustering system C_N of some rooted level-k network N. For the Hasse diagram H = H[C], it defines for each non-trivial block B a parameter μ(B) as the size of a minimum family of clusters generating all overlap-intersections inside B. The main theorem asserts that a realizing level-k network exists if and only if μ(B) ≤ k for every non-trivial block B. Necessity is argued by showing that overlap-intersection pieces must be realized by distinct non-root hybrid vertices; sufficiency is proved constructively by iteratively splitting selected hybrid vertices in the Hasse diagram while preserving the hardwired clusters and bounding the resulting level by the block-wise μ values.

Significance. If the central iff statement holds, the result supplies a direct, combinatorial test for the minimal level required by any realizing network, computed solely from the input clustering system via its Hasse diagram. The constructive sufficiency argument further supplies an explicit procedure for building a realizing network whose level is controlled by μ, which is a concrete algorithmic contribution to phylogenetic network theory.

major comments (1)

[Necessity proof of the main theorem] Necessity proof of the main theorem: the argument that every overlap-intersection piece inside a block must be represented by a distinct non-root hybrid vertex is load-bearing for the claimed equality between μ(B) and the minimal level. It is not shown why a single hybrid vertex (or the root) cannot simultaneously realize multiple such pieces while still producing exactly the prescribed hardwired clusters; if such sharing is possible, then μ(B) would strictly overestimate the required level and the necessity direction would fail. A concrete argument ruling out shared or root-encoded realizations, or an explicit small example demonstrating that any realizing block must use at least μ(B) non-root hybrids, is needed.

minor comments (1)

[Definition of μ(B)] An explicit worked example computing μ(B) for a small non-trivial block (including the minimum generating family and the resulting overlap-intersections) would make the definition of μ immediately verifiable for readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying a point where the necessity argument in the main theorem can be strengthened. We agree that additional detail is warranted to explicitly rule out the possibility of shared hybrid vertices or root-encoded realizations. Below we respond to the major comment and outline the revisions we will make.

read point-by-point responses

Referee: Necessity proof of the main theorem: the argument that every overlap-intersection piece inside a block must be represented by a distinct non-root hybrid vertex is load-bearing for the claimed equality between μ(B) and the minimal level. It is not shown why a single hybrid vertex (or the root) cannot simultaneously realize multiple such pieces while still producing exactly the prescribed hardwired clusters; if such sharing is possible, then μ(B) would strictly overestimate the required level and the necessity direction would fail. A concrete argument ruling out shared or root-encoded realizations, or an explicit small example demonstrating that any realizing block must use at least μ(B) non-root hybrids, is needed.

Authors: We appreciate this observation. The necessity direction (Theorem 3.1) proceeds by associating each minimal generating family of clusters for an overlap-intersection inside B with a distinct reticulation. However, we acknowledge that the current write-up does not contain an explicit sub-argument showing why a single non-root hybrid vertex cannot realize two or more such pieces without either adding extraneous hardwired clusters or omitting required ones. We will insert a new Lemma 3.3 that proves this by contradiction: suppose one hybrid v realizes two distinct overlap-intersections I1 and I2 generated by minimal families F1 and F2; the two incoming edges to v would then force a cluster that properly contains both I1 and I2 while still being compatible with the Hasse diagram, contradicting the minimality of μ(B). A parallel short argument (now Proposition 3.2) shows that the root cannot encode any non-trivial overlap-intersection because its outgoing edges define a partition with no reticulation. We will also add a concrete four-taxon example (Example 3.4) in which μ(B)=2 and every level-1 network either misses a required cluster or produces an extra one. These additions will be placed immediately before the main necessity proof. We therefore mark this revision as accepted. revision: yes

Circularity Check

0 steps flagged

No circularity: combinatorial parameter μ(B) yields independent characterization of network realizability

full rationale

The paper defines μ(B) directly as the size of a minimum generating family for overlap-intersections within each block B of the Hasse diagram H derived from the input clustering system C. The central theorem then states an if-and-only-if criterion for existence of a level-k realization whose hardwired clusters equal C. Necessity is argued via structural constraints on hybrid vertices in any realizing network; sufficiency proceeds by an explicit iterative construction that splits vertices while preserving the clustering system and bounding the level by the precomputed μ values. No parameter is fitted to data and then relabeled as a prediction, no self-citation supplies a load-bearing uniqueness result, and the derivation does not reduce the claimed equivalence to a tautology or renaming of the input. The result is therefore self-contained against the external benchmark of network level.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard finite-set combinatorics and graph-theoretic definitions of Hasse diagrams and hybrid vertices; μ(B) is derived from the input rather than introduced as a free parameter.

axioms (1)

standard math Standard axioms of set theory and partial orders for finite taxa sets and cluster inclusion.
The Hasse diagram H[C] and block decomposition presuppose basic order theory on finite sets.

pith-pipeline@v0.9.0 · 5699 in / 1218 out tokens · 41801 ms · 2026-05-22T02:41:44.021056+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

there exists a rooted level-k network N with C_N = C if and only if μ(B) ≤ k for every non-trivial block B of H
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

μ(B) := min{|K| | K ⊆ C(B) is a generating set of B} where I(B) = {A ∩ A' | A,A' overlap}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Hellmuth, D

M. Hellmuth, D. Schaller, and P. F. Stadler,Clustering systems of phylogenetic networks, Theory in Biosciences, 142 (2023), 301–358. doi:10.1007/s12064-023- 00398-w

work page doi:10.1007/s12064-023- 2023
[2]

D. H. Huson, R. Rupp, and C. Scornavacca,Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press, Cambridge, 2011. doi:10.1017/CBO9780511974076

work page doi:10.1017/cbo9780511974076 2011
[3]

D. H. Huson and C. Scornavacca,A survey of combinatorial methods for phylogenetic networks, Genome Biology and Evolution, 3 (2011), 23–35. doi:10.1093/gbe/evq077

work page doi:10.1093/gbe/evq077 2011
[4]

Nakhleh and L.-S

L. Nakhleh and L.-S. Wang,Phylogenetic networks, trees, and clusters, inCom- putational Science – ICCS 2005, Lecture Notes in Computer Science, Vol. 3515, Springer, Berlin, 2005, pp. 919–926. doi:10.1007/11428848 117

work page doi:10.1007/11428848 2005
[5]

D. H. Huson and R. Rupp,Summarizing multiple gene trees using cluster networks, inAlgorithms in Bioinformatics, Lecture Notes in Computer Science, Vol. 5251, Springer, Berlin, 2008, pp. 296–305. doi:10.1007/978-3-540-87361-7 25

work page doi:10.1007/978-3-540-87361-7 2008
[6]

van Iersel, S

L. van Iersel, S. Kelk, R. Rupp, and D. H. Huson,Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters, Bioinformatics, 26 (2010), i124–i131. doi:10.1093/bioinformatics/btq202

work page doi:10.1093/bioinformatics/btq202 2010
[7]

Gambette and K

P. Gambette and K. T. Huber,On encodings of phylogenetic networks of bounded level, Journal of Mathematical Biology, 65 (2012), 157–180. doi:10.1007/s00285- 011-0456-y 32

work page doi:10.1007/s00285- 2012
[8]

To and M

T.-H. To and M. Habib,Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time, inCombinatorial Pattern Matching, Lec- ture Notes in Computer Science, Vol. 5577, Springer, Berlin, 2009, pp. 275–288. doi:10.1007/978-3-642-02441-2 25

work page doi:10.1007/978-3-642-02441-2 2009
[9]

Gusfield, V

D. Gusfield, V. Bansal, V. Bafna, and Y. S. Song,A decomposition theory for phylogenetic networks and incompatible characters, Journal of Computational Biology, 14 (2007), 1247–1272. doi:10.1089/cmb.2006.0137

work page doi:10.1089/cmb.2006.0137 2007
[10]

J. Wang, M. Guo, X. Liu, Y. Liu, C. Wang, L. Xing, and K. Che,L network: an effi- cient and effective method for constructing phylogenetic networks, Bioinformatics, 29 (2013), 2269–2276. doi:10.1093/bioinformatics/btt378

work page doi:10.1093/bioinformatics/btt378 2013
[11]

Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

C. Semple and M. Steel,Phylogenetics, Oxford University Press, Oxford, 2003. doi:10.1093/oso/9780198509424.001.0001

work page doi:10.1093/oso/9780198509424.001.0001 2003
[12]

Zhang,Clusters, Trees, and Phylogenetic Network Classes, inBioinformatics and Phylogenetics: Seminal Contributions of Bernard Moret, Computational Biology, Vol

L. Zhang,Clusters, Trees, and Phylogenetic Network Classes, inBioinformatics and Phylogenetics: Seminal Contributions of Bernard Moret, Computational Biology, Vol. 29, Springer, Cham, 2019, pp. 277–315. doi:10.1007/978-3-030-10837-3 12

work page doi:10.1007/978-3-030-10837-3 2019
[13]

Baroni, C

M. Baroni, C. Semple, and M. Steel,A framework for representing reticulate evolution, Annals of Combinatorics, 8 (2005), 391–408. doi:10.1007/s00026-004- 0228-0

work page doi:10.1007/s00026-004- 2005
[14]

S. J. Willson,Regular networks can be uniquely constructed from their trees, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8 (2011), 785–796. doi:10.1109/TCBB.2010.69

work page doi:10.1109/tcbb.2010.69 2011
[15]

A. V. Shanavas, M. Changat, M. Hellmuth, and P. F. Stadler,Unique least common ancestors and clusters in directed acyclic graphs, inCALDAM 2024, Lecture Notes in Computer Science, Vol. 14508, Springer, Cham, 2024, pp. 148–161. doi:10.1007/978-3-031-52213-0 11

work page doi:10.1007/978-3-031-52213-0 2024
[16]

Discrete Applied Mathematics 378:584–593, DOI 10.1016/j.dam.2025.08.037

M. Hellmuth and A. Lindeberg,Characterizing and transforming DAGs within the I-LCA framework, Discrete Applied Mathematics, 378 (2026), 584–593. doi:10.1016/j.dam.2025.08.037

work page doi:10.1016/j.dam.2025.08.037 2026
[17]

In: Meersman, R., Panetto, H., Dillon, T., Mis- sikoff, M., Liu, L., Pastor, O., Cuzzocrea, A., Sellis, T

R. Diestel,Graph Theory, 5th ed., Springer, Berlin, 2017. doi:10.1007/978-3-662- 53622-3 33

work page doi:10.1007/978-3-662- 2017

[1] [1]

Hellmuth, D

M. Hellmuth, D. Schaller, and P. F. Stadler,Clustering systems of phylogenetic networks, Theory in Biosciences, 142 (2023), 301–358. doi:10.1007/s12064-023- 00398-w

work page doi:10.1007/s12064-023- 2023

[2] [2]

D. H. Huson, R. Rupp, and C. Scornavacca,Phylogenetic Networks: Concepts, Algorithms and Applications, Cambridge University Press, Cambridge, 2011. doi:10.1017/CBO9780511974076

work page doi:10.1017/cbo9780511974076 2011

[3] [3]

D. H. Huson and C. Scornavacca,A survey of combinatorial methods for phylogenetic networks, Genome Biology and Evolution, 3 (2011), 23–35. doi:10.1093/gbe/evq077

work page doi:10.1093/gbe/evq077 2011

[4] [4]

Nakhleh and L.-S

L. Nakhleh and L.-S. Wang,Phylogenetic networks, trees, and clusters, inCom- putational Science – ICCS 2005, Lecture Notes in Computer Science, Vol. 3515, Springer, Berlin, 2005, pp. 919–926. doi:10.1007/11428848 117

work page doi:10.1007/11428848 2005

[5] [5]

D. H. Huson and R. Rupp,Summarizing multiple gene trees using cluster networks, inAlgorithms in Bioinformatics, Lecture Notes in Computer Science, Vol. 5251, Springer, Berlin, 2008, pp. 296–305. doi:10.1007/978-3-540-87361-7 25

work page doi:10.1007/978-3-540-87361-7 2008

[6] [6]

van Iersel, S

L. van Iersel, S. Kelk, R. Rupp, and D. H. Huson,Phylogenetic networks do not need to be complex: using fewer reticulations to represent conflicting clusters, Bioinformatics, 26 (2010), i124–i131. doi:10.1093/bioinformatics/btq202

work page doi:10.1093/bioinformatics/btq202 2010

[7] [7]

Gambette and K

P. Gambette and K. T. Huber,On encodings of phylogenetic networks of bounded level, Journal of Mathematical Biology, 65 (2012), 157–180. doi:10.1007/s00285- 011-0456-y 32

work page doi:10.1007/s00285- 2012

[8] [8]

To and M

T.-H. To and M. Habib,Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time, inCombinatorial Pattern Matching, Lec- ture Notes in Computer Science, Vol. 5577, Springer, Berlin, 2009, pp. 275–288. doi:10.1007/978-3-642-02441-2 25

work page doi:10.1007/978-3-642-02441-2 2009

[9] [9]

Gusfield, V

D. Gusfield, V. Bansal, V. Bafna, and Y. S. Song,A decomposition theory for phylogenetic networks and incompatible characters, Journal of Computational Biology, 14 (2007), 1247–1272. doi:10.1089/cmb.2006.0137

work page doi:10.1089/cmb.2006.0137 2007

[10] [10]

J. Wang, M. Guo, X. Liu, Y. Liu, C. Wang, L. Xing, and K. Che,L network: an effi- cient and effective method for constructing phylogenetic networks, Bioinformatics, 29 (2013), 2269–2276. doi:10.1093/bioinformatics/btt378

work page doi:10.1093/bioinformatics/btt378 2013

[11] [11]

Oxford Univer- sity Press (2018).https://doi.org/10.1093/oso/9780198814788.001.0001

C. Semple and M. Steel,Phylogenetics, Oxford University Press, Oxford, 2003. doi:10.1093/oso/9780198509424.001.0001

work page doi:10.1093/oso/9780198509424.001.0001 2003

[12] [12]

Zhang,Clusters, Trees, and Phylogenetic Network Classes, inBioinformatics and Phylogenetics: Seminal Contributions of Bernard Moret, Computational Biology, Vol

L. Zhang,Clusters, Trees, and Phylogenetic Network Classes, inBioinformatics and Phylogenetics: Seminal Contributions of Bernard Moret, Computational Biology, Vol. 29, Springer, Cham, 2019, pp. 277–315. doi:10.1007/978-3-030-10837-3 12

work page doi:10.1007/978-3-030-10837-3 2019

[13] [13]

Baroni, C

M. Baroni, C. Semple, and M. Steel,A framework for representing reticulate evolution, Annals of Combinatorics, 8 (2005), 391–408. doi:10.1007/s00026-004- 0228-0

work page doi:10.1007/s00026-004- 2005

[14] [14]

S. J. Willson,Regular networks can be uniquely constructed from their trees, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8 (2011), 785–796. doi:10.1109/TCBB.2010.69

work page doi:10.1109/tcbb.2010.69 2011

[15] [15]

A. V. Shanavas, M. Changat, M. Hellmuth, and P. F. Stadler,Unique least common ancestors and clusters in directed acyclic graphs, inCALDAM 2024, Lecture Notes in Computer Science, Vol. 14508, Springer, Cham, 2024, pp. 148–161. doi:10.1007/978-3-031-52213-0 11

work page doi:10.1007/978-3-031-52213-0 2024

[16] [16]

Discrete Applied Mathematics 378:584–593, DOI 10.1016/j.dam.2025.08.037

M. Hellmuth and A. Lindeberg,Characterizing and transforming DAGs within the I-LCA framework, Discrete Applied Mathematics, 378 (2026), 584–593. doi:10.1016/j.dam.2025.08.037

work page doi:10.1016/j.dam.2025.08.037 2026

[17] [17]

In: Meersman, R., Panetto, H., Dillon, T., Mis- sikoff, M., Liu, L., Pastor, O., Cuzzocrea, A., Sellis, T

R. Diestel,Graph Theory, 5th ed., Springer, Berlin, 2017. doi:10.1007/978-3-662- 53622-3 33

work page doi:10.1007/978-3-662- 2017