Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
Abstract
We develop a unified framework for the exact enumeration and asymptotic analysis of the three most studied classes of phylogenetic networks: tree-child (TC), reticulation-visible (RV) and orchard networks, whose cardinalities satisfy the strict ordering |TCℓ,k|<|RVℓ,k|<|Orchℓ,k| for reticulation number k≥2 (with TCsubsetneqRV and TCsubsetneqOrch, while RV and Orch are incomparable as sets). Using the Chang--Fuchs structural theorem, we derive a two-level master functional equation for the RV bivariate generating function and obtain exact closed-form identities for the differences Δk(ℓ):=|RVℓ,k|−|TCℓ,k| for k=2,3, with the asymptotic universality Δk(ℓ)/|TCℓ,k|∼ k!/ℓ. For orchard networks, we prove a \emph{universal hypergeometric law} that resolves the exact enumeration problem for all ℓ: the column generating function Fℓ(v) is rational with denominator Dℓ(v)=∏j=2ℓ Xj(v), where Xℓ(v) = ∑k=0⌊ℓ/2⌋(−1)k ℓ!/((ℓ−2k)! k!) vk is the matching polynomial of the complete graph Kℓ and a rescaled Jacobi polynomial. This immediately resolves the intractable ℓ=9 case: D9 has degree 20, dominant growth rate ≈40.73, and all spectral roots are positive real. A complete enumeration table is provided extending the published data of Cardona, Ribas and Pons.
Related
- An explicit birth-death-reticulation model for studying the diversification of phylogenetic networks
- Exact and asymptotic enumeration of unrestricted binary phylogenetic networks through automorphism weights
- Best Matches in Phylogenetic Networks
- Exact Counts of Binary Phylogenetic Networks with Four Reticulations
- The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks
BibTeX
@misc{batle2026exact,
title = {{Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy}},
author = {Josep Batle},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.24325},
eprint = {2606.24325},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.24325},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
AU - Josep Batle
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2606.24325
UR - https://arxiv.org/abs/2606.24325
AB - We develop a unified framework for the exact enumeration and asymptotic analysis of the three most studied classes of phylogenetic networks: tree-child (TC), reticulation-visible (RV) and orchard networks, whose cardinalities satisfy the strict ordering |TC_ℓ,k|<|RV_ℓ,k|<|Orch_ℓ,k| for reticulation number k≥2 (with TCsubsetneqRV and TCsubsetneqOrch, while RV and Orch are incomparable as sets). Using the Chang--Fuchs structural theorem, we derive a two-level master functional equation for the RV bivariate generating function and obtain exact closed-form identities for the differences Δ_k(ℓ):=|RV_ℓ,k|−|TC_ℓ,k| for k=2,3, with the asymptotic universality Δ_k(ℓ)/|TC_ℓ,k|∼ k!/ℓ. For orchard networks, we prove a \emph{universal hypergeometric law} that resolves the exact enumeration problem for all ℓ: the column generating function F_ℓ(v) is rational with denominator D_ℓ(v)=∏_j=2^ℓ X_j(v), where X_ℓ(v) = ∑_k=0^⌊ℓ/2⌋(−1)^k ℓ!/((ℓ−2k)! k!) v^k is the matching polynomial of the complete graph K_ℓ and a rescaled Jacobi polynomial. This immediately resolves the intractable ℓ=9 case: D_9 has degree 20, dominant growth rate ≈40.73, and all spectral roots are positive real. A complete enumeration table is provided extending the published data of Cardona, Ribas and Pons.
ER -