Exact and asymptotic enumeration of unrestricted binary phylogenetic networks through automorphism weights
Abstract
Let cPℓ,k be the set of rooted binary phylogenetic networks with ℓ labelled leaves, k reticulations and no parallel edges. We write |cPℓ,k|=Wk(ℓ)+Dk(ℓ), where the weighted count Wk(ℓ) adds the inverse orders of the leaf-fixing automorphism groups and the defect Dk(ℓ) collects the remainder. The weighted count satisfies, for every k, a recursion over the source layers of the tree-component structure that involves neither a list of component graphs nor any distinction between symmetric and asymmetric configurations, and its exponential generating function is a Laurent polynomial in √(1−2x). Automorphism groups of networks are $2$-groups, elementary abelian for k≤5 but not in general. For k≤5 the defect is the weighted count of networks with a distinguished involution, which obeys an extension of the same recursion. An exact symbolic evaluation of the two recursions yields |cPℓ,k| in closed form for k≤5, the case k=5 being new; it reproduces the published counts for k≤4 and corrects a coefficient in a published generating function for k=3. For every k, uniformly over explicit ranges of k, we prove that the non-tree-child networks are a fraction 2k(k−1)/ℓ of the tree-child networks to leading order, which gives the third term of the asymptotic expansion of |cPℓ,k|. We also prove that reticulation-visible networks exceed tree-child networks by the fraction k(k−1)/ℓ, and that a uniformly random network in cPℓ,k has a nontrivial automorphism with probability k(k−1)/(4ℓ3) to leading order.
Related
- Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy
- 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
- The parental parsimony problem on binary, tree-child phylogenetic networks
BibTeX
@misc{batle2026exact,
title = {{Exact and asymptotic enumeration of unrestricted binary phylogenetic networks through automorphism weights}},
author = {Josep Batle},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03856},
eprint = {2610.03856},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03856},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact and asymptotic enumeration of unrestricted binary phylogenetic networks through automorphism weights
AU - Josep Batle
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03856
UR - https://arxiv.org/abs/2610.03856
AB - Let cP_ℓ,k be the set of rooted binary phylogenetic networks with ℓ labelled leaves, k reticulations and no parallel edges. We write |cP_ℓ,k|=W_k(ℓ)+D_k(ℓ), where the weighted count W_k(ℓ) adds the inverse orders of the leaf-fixing automorphism groups and the defect D_k(ℓ) collects the remainder. The weighted count satisfies, for every k, a recursion over the source layers of the tree-component structure that involves neither a list of component graphs nor any distinction between symmetric and asymmetric configurations, and its exponential generating function is a Laurent polynomial in √(1−2x). Automorphism groups of networks are $2$-groups, elementary abelian for k≤5 but not in general. For k≤5 the defect is the weighted count of networks with a distinguished involution, which obeys an extension of the same recursion. An exact symbolic evaluation of the two recursions yields |cP_ℓ,k| in closed form for k≤5, the case k=5 being new; it reproduces the published counts for k≤4 and corrects a coefficient in a published generating function for k=3. For every k, uniformly over explicit ranges of k, we prove that the non-tree-child networks are a fraction 2k(k−1)/ℓ of the tree-child networks to leading order, which gives the third term of the asymptotic expansion of |cP_ℓ,k|. We also prove that reticulation-visible networks exceed tree-child networks by the fraction k(k−1)/ℓ, and that a uniformly random network in cP_ℓ,k has a nontrivial automorphism with probability k(k−1)/(4ℓ^3) to leading order.
ER -