pith. sign in

arxiv: 2606.24325 · v2 · pith:L7YTNKVQnew · submitted 2026-06-23 · 🧮 math.CO · q-bio.PE

Exact Enumeration of Phylogenetic Networks: The Tree-Child, Reticulation-Visible and Orchard Hierarchy

Josep Batle This is my paper

Pith reviewed 2026-07-01 07:04 UTC · model grok-4.3

classification 🧮 math.CO q-bio.PE
keywords phylogenetic networkstree-child networksreticulation-visible networksorchard networksexact enumerationgenerating functionsmatching polynomialshypergeometric identities
0
0 comments X

The pith

Orchard phylogenetic networks have rational column generating functions whose denominators are products of matching polynomials of complete graphs.

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

The paper develops exact enumeration formulas for tree-child, reticulation-visible, and orchard phylogenetic networks, establishing the strict size ordering tree-child smaller than reticulation-visible smaller than orchard for reticulation number at least two. It applies the Chang-Fuchs structural theorem to obtain a two-level master functional equation for the bivariate generating function of reticulation-visible networks together with closed-form expressions for the exact differences from tree-child networks at small reticulation numbers and the associated asymptotic ratio. For orchard networks the central result is a universal hypergeometric law showing that the column generating function in the reticulation variable is always rational with an explicit denominator built from the matching polynomials of complete graphs, which immediately yields the counts for every number of leaves including the previously open case of nine leaves.

Core claim

For orchard networks the column generating function F_ℓ(v) is rational with denominator D_ℓ(v) equal to the product from j equals 2 to ℓ of X_j(v), where each X_ℓ(v) is the matching polynomial of the complete graph K_ℓ given by the alternating sum over k of ℓ factorial over (ℓ minus 2k) factorial k factorial times v to the k; this identity resolves the exact enumeration problem for every ℓ.

What carries the argument

The universal hypergeometric law for orchard networks, whose denominator is the product of the matching polynomials X_j(v) of complete graphs K_j for j from 2 to ℓ.

If this is right

  • Exact closed-form identities exist for the differences |RV_{ℓ,k}| minus |TC_{ℓ,k}| when k equals 2 or 3.
  • The ratio of those differences to the tree-child count is asymptotically k factorial over ℓ for fixed k.
  • The enumeration for ℓ equals 9 is settled by a degree-20 denominator whose dominant growth rate is approximately 40.73 and whose spectral roots are all positive real.
  • The three network classes satisfy the strict cardinality ordering |TC_{ℓ,k}| less than |RV_{ℓ,k}| less than |Orch_{ℓ,k}| for every k at least 2.

Where Pith is reading between the lines

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

  • The same matching-polynomial denominator construction may supply generating functions for other recursively defined network families once an analogous structural decomposition is available.
  • The explicit positivity of all roots for the ℓ equals 9 denominator suggests that the growth rates of orchard networks admit a simple combinatorial interpretation in terms of perfect matchings.
  • The two-level master equation for reticulation-visible networks could be lifted to a three-level equation if a further structural theorem distinguishes orchard networks inside the reticulation-visible class.

Load-bearing premise

The Chang-Fuchs structural theorem applies directly to reticulation-visible networks and permits derivation of the two-level master functional equation.

What would settle it

An explicit count of the number of orchard networks on 10 leaves that fails to satisfy the recurrence or closed form implied by the rational generating function with denominator the product of the first nine matching polynomials.

read the original 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 $|\mathrm{TC}_{\ell,k}|<|\mathrm{RV}_{\ell,k}|<|\mathrm{Orch}_{\ell,k}|$ for reticulation number $k\geq2$ (with $\mathrm{TC}\subsetneq\mathrm{RV}$ and $\mathrm{TC}\subsetneq\mathrm{Orch}$, while $\mathrm{RV}$ and $\mathrm{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 $\Delta_k(\ell):=|RV_{\ell,k}|-|TC_{\ell,k}|$ for $k=2,3$, with the asymptotic universality $\Delta_k(\ell)/|TC_{\ell,k}|\sim k!/\ell$. For orchard networks, we prove a \emph{universal hypergeometric law} that resolves the exact enumeration problem for all $\ell$: the column generating function $F_\ell(v)$ is rational with denominator $D_\ell(v)=\prod_{j=2}^\ell X_j(v)$, where \[ X_\ell(v) = \sum_{k=0}^{\lfloor\ell/2\rfloor}(-1)^k\, \frac{\ell!}{(\ell-2k)!\,k!}\,v^k \] is the matching polynomial of the complete graph $K_\ell$ and a rescaled Jacobi polynomial. This immediately resolves the intractable $\ell=9$ case: $D_9$ has degree 20, dominant growth rate $\approx40.73$, and all spectral roots are positive real. A complete enumeration table is provided extending the published data of Cardona, Ribas and Pons.

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.

Referee Report

0 major / 3 minor

Summary. The manuscript develops a unified framework for exact enumeration of tree-child (TC), reticulation-visible (RV), and orchard phylogenetic networks using the Chang-Fuchs structural theorem. It derives a two-level master functional equation for the RV bivariate generating function, obtains exact closed-form identities for the differences Δ_k(ℓ) = |RV_{ℓ,k}| - |TC_{ℓ,k}| when k=2,3 together with the asymptotic Δ_k(ℓ)/|TC_{ℓ,k}| ∼ k!/ℓ, and proves a universal hypergeometric law for orchard networks: the column generating function F_ℓ(v) is rational with denominator D_ℓ(v) = ∏_{j=2}^ℓ X_j(v), where X_ℓ(v) is the matching polynomial of K_ℓ (also a rescaled Jacobi polynomial). The work resolves the ℓ=9 case explicitly and supplies an extended enumeration table.

Significance. If the derivations hold, the results supply the first explicit rational generating functions and closed-form difference identities for these classes, resolving previously intractable cases such as ℓ=9 (where D_9 has degree 20 and dominant growth ≈40.73) and extending published tables. The universal hypergeometric law for orchard networks and the asymptotic universality for RV-TC differences constitute concrete, falsifiable advances in combinatorial enumeration of phylogenetic networks.

minor comments (3)
  1. [§3] §3 (or wherever the two-level master functional equation appears): the equation should be displayed explicitly rather than only described, to allow direct verification of the subsequent difference identities for k=2,3.
  2. [Introduction] The statement that RV and Orch are incomparable as sets is asserted without a concrete counter-example pair; a small explicit example (e.g., for ℓ=4 or 5) would strengthen the claim.
  3. [Enumeration table] Table of enumerations: the new entries for ℓ=9 should be accompanied by a brief note on how they were obtained from the rational generating function (e.g., coefficient extraction routine or recurrence).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation of minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on the external Chang-Fuchs structural theorem to obtain the two-level master functional equation for reticulation-visible networks, followed by standard generating-function manipulations to produce closed-form differences and the rational column generating function for orchard networks whose denominator is the product of independently defined matching polynomials X_j(v) of complete graphs K_j. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the universal hypergeometric law is presented as an explicit, verifiable identity derived from the structural theorem and combinatorial enumeration, rendering the chain self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the applicability of the Chang-Fuchs structural theorem and standard techniques of bivariate generating functions and matching polynomials; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption Chang-Fuchs structural theorem holds for reticulation-visible networks
    Invoked to obtain the two-level master functional equation for the RV bivariate generating function.

pith-pipeline@v0.9.1-grok · 5894 in / 1255 out tokens · 45133 ms · 2026-07-01T07:04:19.694886+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 5 canonical work pages · 1 internal anchor

  1. [1]

    Batle J, Pons M (2026) An operator-theoretic proof of the enumeration formula for tree- child networks.Preprint. Bull. Math. Biol. 44

    2026

  2. [2]

    Cardona G, Pons JC, Ribas G, Mart´ ınez Coronado T (2024) Comparison of orchard net- works using their extendedµ-representation.IEEE/ACM Trans Comput Biol Bioinform 21(3):501–507

    2024

  3. [4]

    arXiv:2601.09551v2 [math.CO]

    Lin Z, Liu F, Liu J, Liu J, Xin G (2026) Proof of a conjecture on Young tableaux with walls. arXiv:2601.09551v2 [math.CO]

    work page arXiv 2026

  4. [5]

    In:Proceedings of AofA 2026 (37th Interna- tional Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms), LIPIcs, Vol

    Liu H, Wallner M, Yu G-R (2026) A combinatorial framework for the Pons–Batle identity: Young tableaux, lattice paths, and limit laws. In:Proceedings of AofA 2026 (37th Interna- tional Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms), LIPIcs, Vol. 381, Article 26

    2026

  5. [6]

    Berlekamp ER (1967) Nonbinary BCH decoding.IEEE Trans Inform Theory14:242

    1967

  6. [7]

    IEEE/ACM Trans Comput Biol Bioinform6(4):552–569

    Cardona G, Rossell´ o F, Valiente G (2009) Comparison of tree-child phylogenetic networks. IEEE/ACM Trans Comput Biol Bioinform6(4):552–569

    2009

  7. [8]

    arXiv:2401.08958

    Chang Y-S, Fuchs M (2024) Counting phylogenetic networks with few reticulation vertices. arXiv:2401.08958

    work page arXiv 2024

  8. [9]

    Gunawan ADM, Yan H, Zhang L (2019) Compression of phylogenetic networks and algo- rithm for the tree containment problem.J Comput Biol26(3):285–294

    2019

  9. [10]

    Gordon and Breach, New York

    Chihara TS (1978)An Introduction to Orthogonal Polynomials. Gordon and Breach, New York

    1978

  10. [11]

    arXiv:2307.16252

    Cardona G, Ribas G, Pons JC (2023) Generation of orchard and tree-child networks. arXiv:2307.16252

    work page arXiv 2023

  11. [12]

    Cambridge University Press

    Flajolet P, Sedgewick R (2009)Analytic Combinatorics. Cambridge University Press

    2009

  12. [13]

    Cambridge University Press

    Huson DH, Rupp R, Scornavacca C (2010)Phylogenetic Networks. Cambridge University Press

    2010

  13. [14]

    Massey JL (1969) Shift-register synthesis and BCH decoding.IEEE Trans Inform Theory 15(1):122–127

    1969

  14. [15]

    Comment Math Helv1:227–254

    Plancherel M, Rotach W (1929) Sur les valeurs asymptotiques des polynˆ omes d’Hermite. Comment Math Helv1:227–254

    1929

  15. [16]

    Pons M, Batle J (2021) Combinatorial characterization of tree-child networks.Sci Rep 11:21875

    2021

  16. [17]

    Steel M (2016)Phylogeny: Discrete and Random Processes in Evolution. SIAM

    2016

  17. [18]

    van Iersel L, Janssen R, Jones M, Murakami Y (2022) Orchard networks are trees with additional horizontal arcs.Bull Math Biol84(8):76

    2022

  18. [19]

    Francis and M

    A. Francis and M. Hendriksen, Counting spinal phylogenetic networks, arXiv:2502.14223 (2025)

    work page arXiv 2025

  19. [20]

    G. X. Viennot, Heaps of pieces, I: basic definitions and combinatorial lemmas, inCombi- natoire ´ enum´ erative, Lecture Notes in Math.1234, Springer (1986), 321–350

    1986

  20. [21]

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

    P. Vives, A. de Mier, G. Cardona, and J. C. Pons, Counting spinal tree-child networks via word encodings and generating functions, arXiv:2605.10926 (2026). Bull. Math. Biol. 45 Table 10:Three-class comparison|TC ℓ,k| ≤ |RV ℓ,k| ≤ |Orch ℓ,k|fork= 2 (upper block) andk= 3 (lower block). TC values from the Pons–Batle formula [16]; RV values from the Chang–Fuc...

    work page internal anchor Pith review Pith/arXiv arXiv 2026