Pith. sign in

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 →

arxiv 1908.01917 v3 pith:XBEE2KYU submitted 2019-08-06 q-bio.PE

classification q-bio.PE MSC 05A1505C3092D15
keywords tree-childnetworksphylogeneticcomponentgraphsgalledtreesenumerationexactcountingnormal
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims to solve the previously open problem of exactly counting rooted binary tree-child networks. The count is reduced to enumerating the component graphs that remain after compressing each network by its tree components, and the paper derives formula (11) for the number of tree-child networks with $m$ reticulations on $n$ taxa. Using it, the authors compute the first exact totals on eight taxa. They also give explicit closed formulas for galled trees, normal galled trees, one-component networks, and the distinct network classes with one or two reticulations.

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$.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [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 ...'.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities appear: the paper counts labeled combinatorial objects exactly. The derivations rest on standard enumeration theorems and on the structural characterization of tree-child networks via tree components.

assumptions (4)
  • standard math Erdos and Szekely's enumeration of rooted trees by degree sequence
    Used without proof in Theorem 4 to count ordered trees with prescribed numbers of internal nodes of each degree.
  • standard math Semple and Steel's Theorem 2.8.3 for unrooted phylogenetic tree counts under edge attachment
    Used in Proposition 6 to count one-component galled trees via unrooted tree generation.
  • standard math Generating function identity f(x) = (1-4x)^(-1/2) for central binomial coefficients
    Used in Lemma 20 to evaluate the sums needed for the two-reticulation formulas.
  • domain assumption Binary rooted phylogenetic network structural definitions and the component graph decomposition give a bijection for tree-child networks
    The counting method in Section 4 relies on the claim that every tree-child network corresponds uniquely to a component graph plus an expansion; the paper cites component graph notions from prior work and builds on them.

how reviews work

0 comments
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 reproduced from arXiv: 1908.01917 by the authors.

Figure 1
Figure 1. 4 1 2 3 5 2 3 𝑟3 4 𝑟1 5 𝑟2 1 𝐶0 𝐶1 𝐶2 𝐶3 {1, 5} {3} {4} {2} [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Illustration of transformation from a rooted, ordered tree to a set of galled trees. The ordered tree has the internal nodes a and b. The node a has three children ordered from left to right. It can be mapped to one of the three possible galls (shaded in the first column). The node b has two children ordered from left to right. The node can remain as a binary node or be mapped to one of the two possible galls (shade… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Illustration of the proof of Proposition 6. A. Insert a leaf into the edge leading to another leaf in a tree generates a galled tree with one reticulation if the two leaves are not in a cherry. B. Edge attachment merges two unrooted trees by inserting an edge between a…
Figure 5
Figure 5. Figure 5: Illustration of reticulation insertions and deletions. There are two types of insertions and deletions in tree-child networks: The added or removed reticulation straddles two tree edges (left) or is attached onto a single tree edge (right). 13 [PITH_FULL_IMAGE:figures…
Figure 6
Figure 6. Figure 6: The component graph of the TCN in Figure 1b. The TCN has four components (left). C0 consists of six internal tree nodes, Leaf 1 and Leaf 5; C2 contains an internal node and Leaf 3; C1 and C3 contain only a single leaf. In the component graph (right) each tree-component…
Figure 7
Figure 7. Figure 7: Illustration of graph extension. G (blue) consists of two parallel edges from node a to node b. It can be extended into eight non-isomorphic labeled DAGs of level 3 by adding two new leaves. • Adding s new nodes v1, v2, · · · , vs, and • Adding two directed edges (ua, …
Figure 8
Figure 8. Figure 8: List of 18 unlabeled component graphs with 1 to 4 nodes. The graphs are listed in increasing order according to level, in which the nodes are arranged row by row. The number below each structure is the number of corresponding labeled component graphs. Proof. Both α1(1)…
Figure 9
Figure 9. Figure 9: List of 82 unlabeled component graphs with 5 nodes. The graphs are listed in increasing order according to level. The nodes of each graph are arranged row by row. The number below each structure is the number of corresponding labeled component graphs. There are 10 stru…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Gusfield, ReCombinatorics: the algorithmics of ancestral recombina- tion graphs and explicit phylogenetic networks, MIT press, 2014

    D. Gusfield, ReCombinatorics: the algorithmics of ancestral recombina- tion graphs and explicit phylogenetic networks, MIT press, 2014

  2. [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

  3. [3]

    D. H. Huson, R. Rupp, V. Berry, P. Gambette, C. Paul, Computing galled networks from real data, Bioinform. 25 (12) (2009) i85–i93

  4. [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

  5. [5]

    Quantifying Genetic Innovation: Mathematical Foundations for the Topological Study of Reticulate Evolution

    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. [6]

    Cardona, F

    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

  7. [7]

    Gusfield, S

    D. Gusfield, S. Eddhu, C. Langley, The fine structure of galls in phylo- genetic networks, INFORMS J. Comput. 16 (4) (2004) 459–469

  8. [8]

    L. Wang, K. Zhang, L. Zhang, Perfect phylogenetic networks with re- combination, J. Comput. Biol. 8 (1) (2001) 69–78. 33

Show all 33 references
  1. [9]

    S. J. Willson, Unique determination of some homoplasies at hybridiza- tion events, Bull. Math. Biol. 69 (5) (2007) 1709–1725

  2. [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

  3. [11]

    D. H. Huson, R. Rupp, C. Scornavacca, Phylogenetic networks: con- cepts, algorithms and applications, Cambridge University Press, 2010

  4. [12]

    A. R. Francis, M. Steel, Which phylogenetic networks are merely trees with additional arcs?, Syst. Biol. 64 (5) (2015) 768–777

  5. [13]

    Zhang, On tree-based phylogenetic networks, J

    L. Zhang, On tree-based phylogenetic networks, J. Comput. Biol. 23 (7) (2016) 553–565

  6. [14]

    Steel, Phylogeny: discrete and random processes in evolution, SIAM, 2016

    M. Steel, Phylogeny: discrete and random processes in evolution, SIAM, 2016

  7. [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

  8. [16]

    Bordewich, C

    M. Bordewich, C. Semple, Reticulation-visible networks, Adv. Appl. Math 78 (2016) 114–141

  9. [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

  10. [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

  11. [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

  12. [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

  13. [21]

    McDiarmid, C

    C. McDiarmid, C. Semple, D. Welsh, Counting phylogenetic networks, Ann. Comb. 19 (1) (2015) 205–224

  14. [22]

    Semple, M

    C. Semple, M. Steel, Unicyclic networks: compatibility and enumera- tion, IEEE/ACM Trans. Comput. Biol. and Bioinform. 3 (1) (2006) 84

  15. [23]

    Bouvel, P

    M. Bouvel, P. Gambette, M. Mansouri, Counting level-k phylogenetic networks, Manuscript

  16. [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

  17. [25]

    Cardona, J

    G. Cardona, J. C. Pons, C. Scornavacca, Generation of binary tree-child phylogenetic networks, PLOS Computational Biology 15 (9) (2019) 1–

  18. [26]

    A. D. Gunawan, J. Rathin, L. Zhang, Counting and enumerating galled networks, arXiv preprint arXiv:1812.08569

  19. [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

  20. [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

  21. [29]

    doi:10.1371/journal.pcbi.1007347

  22. [30]

    Semple, M

    C. Semple, M. Steel, Phylogenetics, Oxford University Press, U.K., 2003

  23. [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

  24. [32]

    URL http://www.sagemath.org

    The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.7) (2019). URL http://www.sagemath.org

  25. [33]

    R. P. Stanley, Enumerative combinatorics. Vol. I, Cole Advanced Books & Software, Monterey, CA, 1986. 35

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.