arxiv: 2605.10926 · v1 · submitted 2026-05-11 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Counting Spinal Tree-Child Networks via Word Encodings and Generating Functions

Pau Vives , Anna de Mier , Gabriel Cardona , Joan Carles Pons

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:18 UTC · model grok-4.3

classification 🧮 math.CO

keywords spinal tree-child networksphylogenetic networkscombinatorial enumerationword encodingsgenerating functionssymbolic methodrecursive specificationtree-child networks

0 comments

The pith

Spinal tree-child phylogenetic networks can be counted exactly by mapping unlabeled instances to restricted words with fixed multiplicities modulo relabeling, or by extracting coefficients from a solvable bivariate generating function built

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

The paper sets out to count spinal tree-child phylogenetic networks, a restricted class in which every internal vertex lies on one path from the root to a leaf. It does so with a word model in which these unlabeled networks become restricted words of fixed letter multiplicities, counted up to a simple relabeling equivalence that produces an explicit formula. Separately, it gives a recursive specification on marked trees whose boxed-product translation produces a bivariate generating function whose coefficients are obtained directly. A reader would care because exact counts make the combinatorial landscape of these evolutionary networks concrete rather than merely simulated or enumerated by computer search.

Core claim

Unlabeled spinal networks correspond to a suitable class of restricted words with fixed multiplicities, taken modulo a simple relabeling equivalence, which yields an explicit closed enumeration. The symbolic-method approach based on a marked version of trees admits a clean recursive specification whose boxed-product translation leads to a solvable bivariate generating function and a direct derivation of the coefficients.

What carries the argument

The word model that encodes unlabeled spinal networks as restricted words with fixed multiplicities modulo relabeling equivalence, together with the marked-tree recursive specification translated by boxed products into a solvable bivariate generating function.

If this is right

An explicit closed-form expression enumerates the unlabeled spinal networks of any size.
The bivariate generating function supplies a direct route to the coefficient sequence without iterative solution of functional equations.
The two independent methods supply mutual verification of the same enumeration.
Spinal networks, being the subclass in which all internal vertices lie on a single root-to-leaf path, admit simpler exact counting than arbitrary tree-child networks.

Where Pith is reading between the lines

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

The same word-encoding technique could be tested on other path-restricted subclasses of phylogenetic networks to see whether similar closed formulas appear.
The explicit counts make it feasible to build uniform random generators or to compute asymptotic densities for spinal networks in larger evolutionary models.

Load-bearing premise

The word model and the marked-tree recursive specification together capture every spinal tree-child network exactly once, with neither omissions nor overcounts.

What would settle it

An exhaustive enumeration of all spinal tree-child networks on four or five leaves that produces numbers different from those given by the closed word formula or by the coefficients of the derived generating function.

Figures

Figures reproduced from arXiv: 2605.10926 by Anna de Mier, Gabriel Cardona, Joan Carles Pons, Pau Vives.

**Figure 1.** Figure 1: Two phylogenetic networks N1 and N2 on [4] and [5], respectively. Square nodes represent reticulations, while circular nodes represent internal tree vertices (the root and leaves are also drawn as circles), with arcs directed downwards. Observe that N1 is not tree-child, since the vertex u has only reticulation children, whereas N2 is tree-child. A phylogenetic network N is tree-child if every internal ver… view at source ↗

**Figure 2.** Figure 2: for an illustration of the path components of a network. • Step 3. We now assign labels from the alphabet {a1, . . . , an−1} to some of the vertices of N. We emphasize that the labeling is not injective (different nodes will get the same label) and not all vertices of N will be labeled. The labeling is defined as follows: – For each i = 1, . . . , k, the reticulation vertex uℓi , and both of its parents ar… view at source ↗

**Figure 2.** Figure 2: Example of the encoding process described in the proof of Proposition 5 for a spinal tree-child network with n = 5 and k = 2: (a) unlabeled network, (b) identification of nodes, (c) decomposition into path components, and (d) partial labeling of the nodes over the alphabet {a1, a2, a3, a4}. Proposition 6. For n ≥ 1 and k ≤ n we have |C 1 n,k/∼| = (n + k)! 2 k(n − k)! k! . Proof. Let w ∈ C 1 n,k. Recall tha… view at source ↗

**Figure 3.** Figure 3: Example of the labeling of interior nodes proposed in [FH25] for the [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

**Figure 4.** Figure 4: Example of a spinal caterpillar network and its decomposition into path components. Now we will introduce a result analogous to Proposition 6, that gives an explicit formula for |C 2 n,k/∼|. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗

**Figure 5.** Figure 5: Depiction of the process of obtaining the marked version of a spinal [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗

**Figure 6.** Figure 6: Depiction of the process of obtaining a cherry spinal tree-child network [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗

read the original abstract

We study the enumeration of spinal tree-child phylogenetic networks, a rigid family of tree-child networks in which all internal vertices lie on a single root--to--leaf path. We provide two complementary combinatorial frameworks. First, we introduce a word model: unlabeled spinal networks correspond to a suitable class of restricted words with fixed multiplicities, taken modulo a simple relabeling equivalence, which yields an explicit closed enumeration. Second, we develop a symbolic-method approach based on a marked version of trees that admits a clean recursive specification; its boxed-product translation leads to a solvable bivariate generating function and a direct derivation of the coefficients.

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

read the letter

Spinal tree-child networks get explicit closed-form counts from a word encoding modulo relabeling and from a solvable bivariate generating function on marked trees, with both matching exhaustive checks up to n=6. The word approach represents the unlabeled networks as restricted words with fixed letter multiplicities, then divides by the symmetry from relabeling the non-spinal leaves to produce a multinomial formula. The generating-function side marks a version of trees, writes a clean recursive specification, translates it via the boxed product into a bivariate equation, and extracts coefficients by iteration. The two constructions agree with each other and with brute-force enumeration for small sizes, which is the strongest evidence that the models are accurate and complete for this class. This is a focused extension of earlier enumeration work on broader tree-child networks, and the explicit formulas plus the verification are the useful parts. The methods themselves are standard combinatorial tools applied to a rigid subclass where all internal vertices lie on one root-to-leaf path, so the paper stays narrow. No load-bearing gaps appear in the constructions described, and the small-case agreement reduces the usual worry about overcounting or omissions. The scope means it will mainly interest people already working on phylogenetic network enumeration or algebraic combinatorics on graphs with biological motivation. For that audience the closed forms and the generating-function derivation are worth having on record. I would send it to referees because the claims are concrete, the checks are there, and the math is grounded enough to benefit from external eyes on the details.

Referee Report

1 major / 2 minor

Summary. The paper enumerates unlabeled spinal tree-child phylogenetic networks via two complementary frameworks. The first maps them to restricted words over a fixed alphabet with prescribed letter multiplicities, taken modulo relabeling of non-spinal leaves, yielding an explicit closed-form count given by a multinomial coefficient divided by a symmetry factor. The second uses a marked-tree recursive specification translated via the boxed product into a bivariate generating function whose functional equation is solved iteratively to extract the same coefficients. Both constructions are verified by exhaustive enumeration for n ≤ 6.

Significance. If the bijections and recursive specifications hold, the work supplies the first explicit, parameter-free enumeration for this rigid subclass of tree-child networks, which is of interest in combinatorial phylogenetics. Strengths include the explicit word-to-network correspondence, the solvable generating function obtained without fitted parameters, and the small-n exhaustive checks confirming exact agreement with no omissions or overcounts.

major comments (1)

The central claim that the word model gives a bijection (and thus the closed multinomial formula) rests on the correspondence between spinal networks and the restricted words modulo relabeling; while the manuscript states the mapping and verifies it for n ≤ 6, a self-contained general proof of injectivity and surjectivity (beyond the small-n check) would make the enumeration fully rigorous.

minor comments (2)

In the symbolic-method section, the precise definition of the boxed product and the iteration scheme for solving the bivariate functional equation could be expanded with one additional displayed equation to improve readability.
The manuscript would benefit from a short table comparing the closed-form counts, the generating-function coefficients, and the exhaustive enumeration for n = 3 to 6.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review, positive assessment, and recommendation of minor revision. We address the single major comment below.

read point-by-point responses

Referee: The central claim that the word model gives a bijection (and thus the closed multinomial formula) rests on the correspondence between spinal networks and the restricted words modulo relabeling; while the manuscript states the mapping and verifies it for n ≤ 6, a self-contained general proof of injectivity and surjectivity (beyond the small-n check) would make the enumeration fully rigorous.

Authors: We agree that a self-contained general proof of injectivity and surjectivity for the word-to-network correspondence would strengthen the rigor of the closed-form enumeration. In the revised manuscript we will insert an explicit proof in the word-model section. The argument constructs the inverse encoding (recovering the spinal path and attaching subtrees from the word multiplicities) and shows that distinct networks produce inequivalent words while every valid word arises from exactly one network up to the stated relabeling. This replaces reliance on the n ≤ 6 verification for the general case and leaves the stated counts unchanged. revision: yes

Circularity Check

0 steps flagged

No significant circularity; explicit bijections and independent GF solution

full rationale

The paper supplies two independent combinatorial constructions for counting spinal tree-child networks. The word model encodes networks as restricted words with fixed multiplicities, quotiented by relabeling, yielding an explicit multinomial formula. The symbolic-method approach uses a marked-tree recursive specification translated via boxed product to a bivariate generating function solved by iteration. Both are cross-verified by exhaustive enumeration for n ≤ 6, confirming agreement without omissions. No load-bearing self-citations, fitted parameters renamed as predictions, or self-definitional reductions appear; the derivations rest on standard combinatorial specifications and direct bijections that are externally checkable.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper applies standard combinatorial enumeration techniques to a defined subclass of networks without introducing new free parameters, ad-hoc axioms, or postulated entities beyond the existing definition of spinal tree-child networks.

pith-pipeline@v0.9.0 · 5400 in / 1041 out tokens · 50853 ms · 2026-05-12T03:18:32.129831+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/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

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

We introduce a word model: unlabeled spinal networks correspond to a suitable class of restricted words with fixed multiplicities, taken modulo a simple relabeling equivalence... symbolic-method approach based on a marked version of trees... boxed-product translation leads to a solvable bivariate generating function

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

45 extracted references · 45 canonical work pages

[1]

arXiv preprint arXiv:2601.09551 , year=

Proof of a Conjecture on Young Tableaux with Walls , author=. arXiv preprint arXiv:2601.09551 , year=

work page arXiv
[2]

PLoS computational biology , volume=

Generation of binary tree-child phylogenetic networks , author=. PLoS computational biology , volume=. 2019 , publisher=

work page 2019
[3]

arXiv preprint arXiv:1803.11325 , year=

Counting phylogenetic networks with few reticulation vertices: tree-child and normal networks , author=. arXiv preprint arXiv:1803.11325 , year=

work page arXiv
[4]

Molecular biology and evolution , volume=

Application of phylogenetic networks in evolutionary studies , author=. Molecular biology and evolution , volume=. 2006 , publisher=

work page 2006
[5]

International journal for parasitology , volume=

Networks in phylogenetic analysis: new tools for population biology , author=. International journal for parasitology , volume=. 2005 , publisher=

work page 2005
[6]

arXiv preprint arXiv:2006.15784 , year=

Counting phylogenetic networks with few reticulation vertices: exact enumeration and corrections , author=. arXiv preprint arXiv:2006.15784 , year=

work page arXiv 2006
[7]

Discrete Applied Mathematics , volume=

Counting phylogenetic networks with few reticulation vertices: a second approach , author=. Discrete Applied Mathematics , volume=. 2022 , publisher=

work page 2022
[8]

Discrete Applied Mathematics , volume=

Counting and enumerating galled networks , author=. Discrete Applied Mathematics , volume=. 2020 , publisher=

work page 2020
[9]

Journal of mathematical biology , volume=

Counting phylogenetic networks of level 1 and 2 , author=. Journal of mathematical biology , volume=. 2020 , publisher=

work page 2020
[10]

Journal of Computer and System Sciences , volume=

Counting and enumerating tree-child networks and their subclasses , author=. Journal of Computer and System Sciences , volume=. 2020 , publisher=

work page 2020
[11]

2009 , publisher=

Analytic combinatorics , author=. 2009 , publisher=

work page 2009
[12]

arXiv preprint arXiv:2502.14223 , year=

Counting spinal phylogenetic networks , author=. arXiv preprint arXiv:2502.14223 , year=

work page arXiv
[13]

Scientific reports , volume=

Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks , author=. Scientific reports , volume=. 2021 , publisher=

work page 2021
[14]

European Journal of Combinatorics , volume=

On the asymptotic growth of the number of tree-child networks , author=. European Journal of Combinatorics , volume=. 2021 , publisher=

work page 2021
[15]

Advances in Applied Mathematics , volume=

Enumerative and distributional results for d-combining tree-child networks , author=. Advances in Applied Mathematics , volume=. 2024 , publisher=

work page 2024
[16]

Journal of Mathematical Biology , volume=

Phylogenetic network classes through the lens of expanding covers , author=. Journal of Mathematical Biology , volume=. 2024 , publisher=

work page 2024
[17]

arXiv preprint arXiv:2110.03842 , year=

A short note on the exact counting of tree-child networks , author=. arXiv preprint arXiv:2110.03842 , year=

work page arXiv
[18]

Advances in Applied Mathematics , volume=

A unifying characterization of tree-based networks and orchard networks using cherry covers , author=. Advances in Applied Mathematics , volume=. 2021 , publisher=

work page 2021
[19]

Systematic biology , volume=

Which phylogenetic networks are merely trees with additional arcs? , author=. Systematic biology , volume=. 2015 , publisher=

work page 2015
[20]

2010 , publisher=

Phylogenetic networks: concepts, algorithms and applications , author=. 2010 , publisher=

work page 2010
[21]

Genes , volume=

Testing for polytomies in phylogenetic species trees using quartet frequencies , author=. Genes , volume=. 2018 , publisher=

work page 2018
[22]

Avian Research , volume=

Multispecies hybridization in birds , author=. Avian Research , volume=. 2019 , publisher=

work page 2019
[23]

Theoretical Computer Science , volume=

On the existence of a cherry-picking sequence , author=. Theoretical Computer Science , volume=. 2018 , publisher=

work page 2018
[24]

Trends in Genetics , volume=

Networks: expanding evolutionary thinking , author=. Trends in Genetics , volume=. 2013 , publisher=

work page 2013
[25]

IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume=

Comparison of tree-child phylogenetic networks , author=. IEEE/ACM Transactions on Computational Biology and Bioinformatics , volume=. 2008 , publisher=

work page 2008
[26]

Theoretical Computer Science , volume=

On cherry-picking and network containment , author=. Theoretical Computer Science , volume=. 2021 , publisher=

work page 2021
[27]

Mathematical Biosciences , year =

Erd. Mathematical Biosciences , year =

work page
[28]

SIAM Journal on Discrete Mathematics , volume=

A structure theorem for rooted binary phylogenetic networks and its implications for tree-based networks , author=. SIAM Journal on Discrete Mathematics , volume=. 2021 , publisher=

work page 2021
[29]

arXiv preprint arXiv:2305.03106 , year=

Making Orchard by Adding Leaves , author=. arXiv preprint arXiv:2305.03106 , year=

work page arXiv
[30]

Journal of Computational Biology , volume=

On tree-based phylogenetic networks , author=. Journal of Computational Biology , volume=. 2016 , publisher=

work page 2016
[31]

IEEE/ACM transactions on computational biology and bioinformatics , volume=

Nonbinary tree-based phylogenetic networks , author=. IEEE/ACM transactions on computational biology and bioinformatics , volume=. 2016 , publisher=

work page 2016
[32]

2016 , publisher=

Phylogeny: discrete and random processes in evolution , author=. 2016 , publisher=

work page 2016
[33]

Journal of Mathematical Biology , volume=

Tree-based networks: characterisations, metrics, and support trees , author=. Journal of Mathematical Biology , volume=. 2019 , publisher=

work page 2019
[34]

Journal of Mathematical Biology , volume=

Classes of explicit phylogenetic networks and their biological and mathematical significance , author=. Journal of Mathematical Biology , volume=. 2022 , publisher=

work page 2022
[35]

Science , volume=

Phylogenetics and the cohesion of bacterial genomes , author=. Science , volume=. 2003 , publisher=

work page 2003
[36]

Genome biology , volume=

The tree of one percent , author=. Genome biology , volume=. 2006 , publisher=

work page 2006
[37]

2000 , publisher=

Molecular evolution and phylogenetics , author=. 2000 , publisher=

work page 2000
[38]

Flajolet Sedgewick, Analytic Combinatorics

work page
[39]

Francis and M

A. Francis and M. Hendriksen, Counting spinal phylogenetic networks, arxiv

work page
[40]

Pons and J

M. Pons and J. Batle, Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks, Nature Publishing Group UK London

work page
[41]

Fuchs, G.-R

M. Fuchs, G.-R. Yu and L. Zhang, On the asymptotic growth of the number of tree-child networks, European Journal of Combinatorics, Elsevier

work page
[42]

Chang, M

Y.-S. Chang, M. Fuchs, H. Liu, W. Wallner and G.-R. Yu, Enumerative and distributional results for d-combining tree-child networks, Advances in Applied Mathematics, Elsevier

work page
[43]

Francis, D

A. Francis, D. Marchei and M. Steel, Phylogenetic network classes through the lens of expanding covers, Journal of Mathematical Biology, Springer

work page
[44]

Fuchs and H

M. Fuchs and H. Liu, A Short Note on the Exact Counting of Tree-Child Networks, arXiv

work page
[45]

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

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

work page