REVIEW 3 major objections 4 minor 33 references
Counting Tree-Child Networks and Their Subclasses
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Counting tree-child networks reduces to counting labeled component graphs.
desk verdict Promising counting formulas, but the central recurrence for component graphs is false as printed and must be fixed before the main claims are accepted. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The key object is the component graph $G(N)$ of a tree-child network: the directed acyclic graph whose nodes are the tree components of $N$ and whose edges record where the parents of each reticulation lie. The paper counts the set $D_m$ of all labeled rooted DAGs with indegree-2 non-root nodes using the recurrence (9), where the coefficient $\beta(m,s,t)$ counts, by inclusion-exclusion, the ways to attach $s$ new leaves to $t$ old leaves so every old leaf receives at least one edge. Formula (11) then expands each component graph by replacing each node with a phylogenetic tree and inserting reticulations along tree edges, giving the number of tree-child networks.
What would settle it
Evaluate recurrence (9) for $m=2$ and $m=3$ and compare with the labeled counts under the component graphs in Figure 8. If, as printed, the recurrence returns $\alpha_2=0$ and $\alpha_3=0$ while Figure 8 shows nonzero counts, the bound $t\le \min(s/2,m-s-1)$ is wrong; correcting it will change every $D_m$ count and hence the totals in Table 3 for all $n$.
Extended reading notes
Core claim
The central discovery is that every tree-child network is uniquely described by two layers: a component graph, a labeled rooted DAG whose non-root nodes have indegree 2, and a collection of one-component tree-child networks attached to its nodes. Counting component graphs is then a row-by-row extension problem solved by recurrence (9), and expanding each component graph by phylogenetic trees with reticulation insertions gives formula (11). This yields exact values for all $k<n\le 8$, including the total $13{,}769{,}649{,}608{,}920$ tree-child networks with at least one reticulation on eight taxa, and the observation that networks with the maximum number $n-1$ of reticulations are exactly twice as numerous as those with $n-2$.
Load-bearing premise
The printed bound $t\le \min(s/2,m-s-1)$ in recurrence (9) is load-bearing for counting component graphs of every size; as written it makes $D_2$ and $D_3$ empty even though Figure 8 lists component graphs with two and three nodes, so the derivation of that bound is the fragile step.
Editorial extensions
If this is right
- Exact counts for tree-child networks on any number of taxa become computable by iterating formulas (9) and (11), rather than by exhaustive generation.
- The component-graph decomposition gives a direct enumeration algorithm for all tree-child networks with $m$ reticulations.
- The first exact totals on eight taxa, including $13{,}769{,}649{,}608{,}920$, provide a concrete benchmark against which asymptotic estimates for large $n$ can be tested.
- The ordered-tree correspondence yields the first formula for the number of normal galled trees.
- Proposition 15 gives a simple doubling relation between the maximum-reticulation layer of tree-child networks and the next layer.
Reading between the lines
- If the component-graph recurrence is repaired, the same machinery should produce exact totals for $n\ge 9$, where no exact counts currently exist.
- The component-graph row construction is a generic device: any class defined by a forbidden pattern on reticulation parents could be counted by adding that pattern as a constraint on $D_m$.
- The near-doubling structure in Proposition 15 suggests that the maximum-reticulation layer of a tree-child network may have an even simpler bijective encoding than the general formula.
- For normal networks, the extra condition that the two parents of each reticulation be incomparable might be representable as a restriction on component graphs, which would turn the open normal-network counting problem into a variant of Theorem 13.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript studies exact enumeration of rooted binary phylogenetic networks in several classes. It gives formulas for galled trees and normal galled trees via a mapping to ordered trees, derives a closed formula for one-component TCNs, introduces component graphs of TCNs, and proposes a recurrence for counting these component graphs. Using that recurrence, formula (11) is presented as the main tool for counting all TCNs with m reticulations on n taxa, with exact totals computed up to eight taxa in Table 3. The paper also derives explicit formulas for TCNs, galled networks, and galled trees with two reticulations, and ends with open problems.
Significance. If the central recurrence is repaired, the paper makes a substantial contribution: it addresses an open problem in exact counting of tree-child networks, provides a component-graph decomposition that appears promising, gives the first exact totals on eight taxa, and supplies reproducible Python/SAGE scripts. The galled-tree and one-component formulas are useful independent results. However, the main counting theorem as printed contains a load-bearing error in the recurrence for component graphs, so the significance of the paper can be assessed only after that error is corrected and the reported counts are re-verified.
major comments (3)
- [Sec. 4.2, Theorem 13, Eq. (9)] The recurrence for α_m(s) is false as printed. With the stated bound t ≤ min(s/2, m−s−1), the sum is empty for m=2 (s=1) and for m=3 (s=1 and s=2), so the recurrence returns α_2=α_3=0, although Figure 8 lists component graphs with two and three nodes. The proof's justification that 'each node u_i is of indegree 2' implies t≤s/2 is incorrect: indegree constrains incoming edges, not the number of newly added outgoing edges from u_i to the new leaves. With s new nodes there are 2s added incoming stubs total, so the necessary condition for every old leaf to receive at least one added edge is t≤2s, not t≤s/2. The case m−s=1 (extending the one-node component D_1, whose unique node is both root and leaf) is also omitted by the condition t≤m−s−1 and must be handled separately.
- [Sec. 4.3, Theorem 14, Eq. (11), Table 3] Because Eq. (11) sums over D_{m+1}, the printed recurrence makes γ_n(1)=γ_n(2)=0 for all n, contradicting the k=1 and k=2 rows of Table 3, e.g. γ_3(1)=21. The central claim that Eq. (11) gives the exact TCN counts is therefore not established as printed. The failure is local and the intended recurrence appears recoverable with the corrected bound t≤2s plus a separate D_1 base case, but the proof must be corrected and the counts in Table 3 and the accompanying scripts must be recomputed or verified against the corrected recurrence.
- [Sec. 4.2, proof of Theorem 13] The proof of Eq. (9) also needs to justify that each labeled DAG in D_m has a unique decomposition into a DAG in D_{m−s} together with a choice of s new leaves. This uniqueness is implicit in the row-by-row construction but is not stated; without it, the recurrence could undercount or overcount. The corrected proof should explicitly argue that removing all leaves of a DAG in D_m leaves a DAG in D_{m−s} and that this operation inverts the stated extension procedure.
minor comments (4)
- [Theorem 4] The display following 'We then have:' is missing a predicate; as printed it reads as a bare summation followed by 'galled trees on [n]' rather than a complete sentence such as 'the number of galled trees on [n] is ...'.
- [Table 3] The caption states 'where 1 ≤ k < n and 3 ≤ n ≤ 8' but the table includes a column for n=2; either include n=2 in the stated range or remove that column.
- [Proof of Proposition 15] The assertion that the two choices for the leaf w 'produce non-isomorphic networks' is stated without argument; a brief justification would make the proof self-contained.
- [Sec. 4.3, after Theorem 14] The downloadable scripts are appreciated, but since the printed recurrence in Eq. (9) differs from what the scripts must implement to produce Table 3, the authors should state explicitly which recurrence the scripts use and why the printed version and the scripted version agree after correction.
Circularity Check
No significant circularity: the TCN counts are obtained from self-contained combinatorial recurrences and checked against external enumeration benchmarks; self-citations supply independent ingredients, not the target counts.
full rationale
The derivation chain is self-contained and does not reduce to its inputs. Theorem 13's recurrence for D_m is an inclusion-exclusion count of labeled rooted DAGs with indegree-2 non-root nodes; the target TCN totals do not appear on the right-hand side, and the later expansion formula (11) composes these counts with independent phylogenetic-tree counts. Theorem 11 for one-component TCNs is proved by a direct edge-insertion count, and Lemma 9 supplies uniqueness of the insertion representation rather than assuming the count. The galled-tree formulas in Theorems 4 and 5 are derived from a many-to-many relation with ordered trees and the Erdős-Székely tree-count theorem, with the over-counting factor explicitly divided out. No fitted parameters or data subsets are used; Table 3 is presented as computed output and is explicitly checked against external Sage/Python scripts and against the earlier enumeration totals of [25]. The only self-citations are Proposition 19, which imports parameter-free formulas for |NN_{n,1}| and |RPN_{n,1}| from [30], and the references to [26] and [25] for auxiliary or benchmark results; these concern different network classes or external enumerations and do not assume the target TCN counts, so they are not circularity. The paper also flags omitted proofs of Proposition 1 and Proposition 12, but those are elementary supporting facts and are not a route by which the desired conclusion is assumed. An honest caveat: the printed bound t <= s/2 in Theorem 13 appears to be a mathematical error that would make D_2 and D_3 empty, contradicting Figure 8; however, an arithmetic or recurrence bug is a correctness concern rather than a circularity, and it does not change the circularity verdict.
Assumptions & free parameters
assumptions (4)
- standard math Erdos and Szekely's enumeration of rooted trees by degree sequence
- standard math Semple and Steel's Theorem 2.8.3 for unrooted phylogenetic tree counts under edge attachment
- standard math Generating function identity f(x) = (1-4x)^(-1/2) for central binomial coefficients
- domain assumption Binary rooted phylogenetic network structural definitions and the component graph decomposition give a bijection for tree-child networks
Cite this review
Pith. "Pith review of Counting Tree-Child Networks and Their Subclasses." pith.science (2026). https://pith.science/paper/XBEE2KYU
@misc{pith2026190801917,
author = {Pith},
title = {Pith review of: Counting Tree-Child Networks and Their Subclasses},
year = {2026},
howpublished = {\url{https://pith.science/paper/XBEE2KYU}},
note = {Machine review of arXiv:1908.01917}
}
read the original abstract
Galled trees are studied as a recombination model in population genetics. This class of phylogenetic networks is generalized into tree-child, galled and reticulation-visible network classes by relaxing a structural condition imposed on galled trees. We count tree-child networks through enumerating their component graphs. Explicit counting formulas are also given for galled trees through their relationship to ordered trees, phylogenetic networks with few reticulations and phylogenetic networks in which the child of each reticulation is a leaf.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
D. Gusfield, ReCombinatorics: the algorithmics of ancestral recombina- tion graphs and explicit phylogenetic networks, MIT press, 2014
work page 2014
-
[2]
R. Jain, M. C. Rivera, J. A. Lake, Horizontal gene transfer among genomes: the complexity hypothesis, Proc. Natl. Acad. Sci. USA 96 (7) (1999) 3801–3806
work page 1999
-
[3]
D. H. Huson, R. Rupp, V. Berry, P. Gambette, C. Paul, Computing galled networks from real data, Bioinform. 25 (12) (2009) i85–i93
work page 2009
-
[4]
D. P. Humphreys, M. R. McGuirl, M. Miyagi, A. J. Blumberg, Fast esti- mation of recombination rates using topological data analysis, Genetics (2019) genetics–301565
work page 2019
-
[5]
M. Lesnick, R. Rabadan, D. I. Rosenbloom, Quantifying genetic inno- vation: Mathematical foundations for the topological study of reticulate evolution, arXiv preprint arXiv:1804.01398
-
[6]
G. Cardona, F. Rossello, G. Valiente, Comparison of tree-child phyloge- netic networks, IEEE/ACM Trans Comput. Biol. and Bioinform. 6 (4) (2009) 552–569
work page 2009
-
[7]
D. Gusfield, S. Eddhu, C. Langley, The fine structure of galls in phylo- genetic networks, INFORMS J. Comput. 16 (4) (2004) 459–469
work page 2004
-
[8]
L. Wang, K. Zhang, L. Zhang, Perfect phylogenetic networks with re- combination, J. Comput. Biol. 8 (1) (2001) 69–78. 33
work page 2001
Show all 33 references
-
[9]
S. J. Willson, Unique determination of some homoplasies at hybridiza- tion events, Bull. Math. Biol. 69 (5) (2007) 1709–1725
2007
-
[10]
D. H. Huson, T. H. Kl¨ opper, Beyond galled trees-decomposition and computation of galled networks, in: Proc. Annual Int. Conf. Res. Com- put. Mol. Biol., Springer, 2007, pp. 211–225
2007
-
[11]
D. H. Huson, R. Rupp, C. Scornavacca, Phylogenetic networks: con- cepts, algorithms and applications, Cambridge University Press, 2010
2010
-
[12]
A. R. Francis, M. Steel, Which phylogenetic networks are merely trees with additional arcs?, Syst. Biol. 64 (5) (2015) 768–777
2015
-
[13]
Zhang, On tree-based phylogenetic networks, J
L. Zhang, On tree-based phylogenetic networks, J. Comput. Biol. 23 (7) (2016) 553–565
2016
-
[14]
Steel, Phylogeny: discrete and random processes in evolution, SIAM, 2016
M. Steel, Phylogeny: discrete and random processes in evolution, SIAM, 2016
2016
-
[15]
Zhang, Clusters, trees and phylogenetic network classes, in: T
L. Zhang, Clusters, trees and phylogenetic network classes, in: T. Warnow (ed.): Bioinformatics and Phylogenetics –Seminal Contribu- tions of Bernard Moret, Springer Nature, Switzerland, 2019, pp. 277– 315
2019
-
[16]
Bordewich, C
M. Bordewich, C. Semple, Reticulation-visible networks, Adv. Appl. Math 78 (2016) 114–141
2016
-
[17]
Gambette, A
P. Gambette, A. D. Gunawan, A. Labarre, S. Vialette, L. Zhang, Lo- cating a tree in a phylogenetic network in quadratic time, in: Proc. Int. Confer. Res. Comput. Mol. Biol., Springer, 2015, pp. 96–107
2015
-
[18]
Gambette, A
P. Gambette, A. D. Gunawan, A. Labarre, S. Vialette, L. Zhang, Solving the tree containment problem in linear time for nearly stable phyloge- netic networks, Discrete Appl. Math. 246 (2018) 62–79
2018
-
[19]
A. D. Gunawan, B. DasGupta, L. Zhang, A decomposition theorem and two algorithms for reticulation-visible networks, Inform. and Comput. 252 (2017) 161–175
2017
-
[20]
Fuchs, B
M. Fuchs, B. Gittenberger, M. Mansouri, Counting phylogenetic net- works with few reticulation vertices: tree-child and normal networks, Australas. J. Combin. 73 (2) (2019) 385–423. 34
2019
-
[21]
McDiarmid, C
C. McDiarmid, C. Semple, D. Welsh, Counting phylogenetic networks, Ann. Comb. 19 (1) (2015) 205–224
2015
-
[22]
Semple, M
C. Semple, M. Steel, Unicyclic networks: compatibility and enumera- tion, IEEE/ACM Trans. Comput. Biol. and Bioinform. 3 (1) (2006) 84
2006
-
[23]
Bouvel, P
M. Bouvel, P. Gambette, M. Mansouri, Counting level-k phylogenetic networks, Manuscript
-
[24]
Chang, W.-K
K.-Y. Chang, W.-K. Hon, S. V. Thankachan, Compact encoding for galled-trees and its applications, in: 2018 Data Compression Conference, IEEE, 2018, pp. 297–306
2018
-
[25]
Cardona, J
G. Cardona, J. C. Pons, C. Scornavacca, Generation of binary tree-child phylogenetic networks, PLOS Computational Biology 15 (9) (2019) 1–
2019
-
[26]
A. D. Gunawan, J. Rathin, L. Zhang, Counting and enumerating galled networks, arXiv preprint arXiv:1812.08569
-
[27]
A. D. Gunawan, H. Yan, L. Zhang, Compression of phylogenetic net- works and algorithm for the tree containment problem, J. Comput. Biol. 26 (3) (2019) 285–294
2019
-
[28]
P. L. Erd˝ os, L. Sz´ ekely, Applications of antilexicographic order. I. An enumerative theory of trees, Adv. Appl. Math 10 (4) (1989) 488–496
1989
-
[29]
doi:10.1371/journal.pcbi.1007347
-
[30]
Semple, M
C. Semple, M. Steel, Phylogenetics, Oxford University Press, U.K., 2003
2003
-
[31]
Zhang, Generating normal networks via leaf insertion and nearest neighbor interchange, arXiv preprint arXiv:1906.12053
L. Zhang, Generating normal networks via leaf insertion and nearest neighbor interchange, arXiv preprint arXiv:1906.12053
1906 arXiv
-
[32]
URL http://www.sagemath.org
The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.7) (2019). URL http://www.sagemath.org
2019
-
[33]
R. P. Stanley, Enumerative combinatorics. Vol. I, Cole Advanced Books & Software, Monterey, CA, 1986. 35
1986
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.