{"id":"bc6e04f2-de10-4ad5-bb19-e664d9a375f5","arxiv_id":"1908.01917","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact enumeration formulas for tree-child networks and galled-tree subclasses are obtained, including a component graph recurrence and new counts on eight taxa.","lead":"This paper derives exact formulas for counting tree-child phylogenetic networks and related classes by decomposing networks into tree components. It gives exact counts on up to eight taxa and closed formulas for one-component networks and networks with one or two reticulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 13's recurrence as printed gives D_2=D_3=∅, so formula (11) cannot currently support the claimed exact TCN counts.","rationale":"The reader's weakest assumption correctly identifies the recurrence for component graphs as the hinge of the paper's central claim. I checked the arithmetic of the printed recurrence: for m=2 and m=3 the stated bounds make the sums in Eq. (9) empty, so α_2 and α_3 both vanish. This is not a subtle asymptotic issue; Figure 8 and the k=1 row of Table 3 are directly contradicted. The logical error in the proof is also clear: the requirement that every old leaf receive at least one new edge gives t≤2s, not t≤s/2, and the D_1 base case is mishandled by the t≤m−s−1 condition. I gave the paper credit for internal evidence that the underlying method is close: formula (11) reproduces the known one-reticulation count when D_2 is supplied, and the earlier n≤7 totals in Table 3 match [25]. But those cross-checks do not compensate for an unstated correction in the central recurrence; they only strengthen the case that the flaw is local. For that reason I keep the reader's CONDITIONAL verdict rather than upgrading to REJECT or ACCEPT.","tokens_in":21155,"tokens_out":23378,"duration_ms":248018,"concrete_test":"Brute-force enumerate D_2 and D_3 over all labeled rooted DAGs with non-root indegree 2 and parallel edges allowed, then evaluate recurrence (8)–(10) as printed. The printed bound t≤min(s/2,m−s−1) makes both sums empty, giving α_2=α_3=0; the enumeration should give α_2=2 and α_3=15, matching the labeled counts in Figure 8. If this discrepancy is confirmed, Theorem 13 as stated is false; a corrected recurrence (t≤min(2s,m−s−1) plus the m−s=1 base case) must be used to recompute Table 3 before the exact TCN counts can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Theorem 13's recurrence for D_m, because Eq. (11) sums over D_{m+1}. As printed, Eq. (9) restricts t to 1≤t≤min(s/2,m−s−1). For m=2, the only extension is from D_1 with s=1,t=1, and min(1/2,0)=0, so α_2=0; for m=3, both possible extensions (s=1,t=1 from D_2 and s=2,t=1 from D_1) are also excluded. The recurrence therefore returns D_2=D_3=∅, contradicting Figure 8, which lists the double-edge 2-node component graph and three 3-node graphs. The proof's justification for t≤s/2 is that each old leaf ui has indegree 2, but indegree is irrelevant to the number of added outgoing stubs; with s new nodes there are 2s incoming stubs, so the correct necessary bound for the requirement that each old leaf receive at least one added edge is t≤2s. There is also an omitted base case: when m−s=1, the isolated root of D_1 is itself a leaf, so the assertion t≤m−s−1 cannot be used to extend D_1. Since formula (11) sums over D_{m+1}, the printed recurrence would make γ_n(1)=0, contradicting Table 3's k=1 row. The counts might survive a local correction, but the proof as written does not establish them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21386,"tokens_out":8073,"duration_ms":85016,"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":[{"comment":"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.","section":"Sec. 4.2, Theorem 13, Eq. (9)"},{"comment":"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.","section":"Sec. 4.3, Theorem 14, Eq. (11), Table 3"},{"comment":"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.","section":"Sec. 4.2, proof of Theorem 13"}],"minor_comments":[{"comment":"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 ...'.","section":"Theorem 4"},{"comment":"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.","section":"Table 3"},{"comment":"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.","section":"Proof of Proposition 15"},{"comment":"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.","section":"Sec. 4.3, after Theorem 14"}],"recommendation":"major_revision","confidential_remarks":"I agree with the stress-test note: the t≤s/2 bound in Theorem 13 is the fragile point and the omission of the D_1 base case is real. The error appears local and fixable, so I would not reject. The manuscript results from the merging of two independent submissions, and the defect sits in the shared Section 4; after correction and re-verification of Table 3, the paper could be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading, but as it stands one load-bearing recurrence is wrong. Theorem 13's recurrence for D_m is the method the authors use to compute the component graphs that feed into the main TCN counting formula (11). As printed, it gives D_2 = D_3 = ∅, contradicting the paper's own Figure 8. The problem is the bound t ≤ min(s/2, m−s−1). The t ≤ s/2 part is not justified: an old leaf's indegree does not constrain how many outgoing edges it can receive in the extension. The necessary condition is t ≤ 2s, since the s new nodes contribute 2s incoming stubs. The t ≤ m−s−1 bound also fails for the base case m−s=1, where the single node of D_1 is itself a leaf. So the recurrence as written cannot produce the Table 3 counts, and the proof does not establish the paper's central claim.\n\nThat said, there is real content here. The galled-tree results in Section 3 are solid: the ordered-tree bijection gives a clean formula and, as far as I can tell, the first formula for normal galled trees. The one-component TCN formula (Theorem 11) is simple and verifiable. Theorem 21's explicit expression for |TC_{n,2}| is a concrete contribution, and Proposition 15 is a nice structural observation. These parts are independently useful, and the citation pattern looks appropriate—the authors build on their own component-graph compression work, which is legitimate.\n\nWhere I land: this is not a desk reject. The flaw is central, but it is a local correction—replace s/2 with 2s, handle the m−s=1 case, and the recurrence likely produces the right D_m. I would want the authors to fix this and either verify the script output or provide a corrected proof before the exact-count claim is accepted. The GitHub scripts are a plus, but I have not rerun them. A competent referee should check the corrected recurrence against Figures 8–9 and the SAGE counts. If the authors make that repair, the paper becomes a solid contribution to phylogenetic combinatorics.","headline":"Promising counting formulas, but the central recurrence for component graphs is false as printed and must be fixed before the main claims are accepted.","tokens_in":21899,"tokens_out":5631,"would_cite":false,"duration_ms":51948,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A15","05C30","92D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Counting tree-child networks reduces to counting labeled component graphs.","keywords":["tree-child networks","phylogenetic networks","component graphs","galled trees","galled networks","enumeration","exact counting","normal networks"],"falsifier":"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$.","tokens_in":20914,"feed_emoji":"🌳","tokens_out":4570,"duration_ms":42730,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact count of tree-child networks found for eight taxa","feed_subtitle":"New component-graph formulas solve the open counting problem and supply totals for all reticulation counts up to eight.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"provides the exhaustive enumeration codes and prior counts for n≤7 that the new Table 3 totals must reproduce and extend.","marker":"[25]"},{"why":"gives the approximate counting results for tree-child and normal networks that this paper replaces with exact formulas.","marker":"[21]"},{"why":"supplies generating functions for tree-child and normal networks with few reticulations, the baseline for the small-k formulas.","marker":"[20]"},{"why":"gives the earlier closed formulas for rooted and unrooted galled trees that the ordered-tree relationship in Section 3 parallels.","marker":"[23]"},{"why":"provides the recurrence approach for counting and enumerating galled networks, reused in the one-component RPN count in Section 5.4.","marker":"[26]"},{"why":"supplies the normal-network and RPN counts with one reticulation that feed the two-reticulation class formulas.","marker":"[30]"}],"fun_headline_variants":["Exact tree-child counts now known for all reticulation numbers up to eight","Component graphs yield exact tree-child counts for up to eight taxa","Counting tree-child networks is now exact up to eight taxa","Tree-child network counting solved for all reticulation counts to eight"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact tree-child counts now known for all reticulation numbers up to eight","Component graphs yield exact tree-child counts for up to eight taxa","Counting tree-child networks is now exact up to eight taxa","Tree-child network counting solved for all reticulation counts to eight"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000955,"raw_usage":{"total_tokens":3979,"prompt_tokens":759,"completion_tokens":3220,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":375,"completion_tokens_details":{"reasoning_tokens":3147}},"tokens_in":375,"tokens_out":3220,"duration_ms":23458,"temperature":1.0,"reasoning_tokens":3147,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:04:40.293886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":"Cardona, J","cited_arxiv_id":null,"evidence_quote":"provides the exhaustive enumeration codes and prior counts for n≤7 that the new Table 3 totals must reproduce and extend."},{"cited_title":"McDiarmid, C","cited_arxiv_id":null,"evidence_quote":"gives the approximate counting results for tree-child and normal networks that this paper replaces with exact formulas."},{"cited_title":"Fuchs, B","cited_arxiv_id":null,"evidence_quote":"supplies generating functions for tree-child and normal networks with few reticulations, the baseline for the small-k formulas."},{"cited_title":"Bouvel, P","cited_arxiv_id":null,"evidence_quote":"gives the earlier closed formulas for rooted and unrooted galled trees that the ordered-tree relationship in Section 3 parallels."},{"cited_title":"Counting and Enumerating Galled Networks","cited_arxiv_id":"1812.08569","evidence_quote":"provides the recurrence approach for counting and enumerating galled networks, reused in the one-component RPN count in Section 5.4."},{"cited_title":"Semple, M","cited_arxiv_id":null,"evidence_quote":"supplies the normal-network and RPN counts with one reticulation that feed the two-reticulation class formulas."}],"review_version":1}