pith. sign in

arxiv: 2606.28539 · v1 · pith:W7B7YJLUnew · submitted 2026-06-26 · 🧮 math.CO

Extremal ranks of unlabeled multifurcating rooted trees in a bijective encoding by the positive integers

Michael R. Doboli , Alessandra R. P. Maranca , Noah A. Rosenberg This is my paper

Pith reviewed 2026-06-30 01:02 UTC · model grok-4.3

classification 🧮 math.CO
keywords multifurcating treesrooted treestree rankingtree balanceextremal ranksbijective encodingphylogenetic treesk-furcating trees
0
0 comments X

The pith

Maximally balanced multifurcating trees attain the lowest ranks and minimally balanced trees the highest ranks in a bijective encoding by positive integers.

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

The paper determines which multifurcating rooted trees with a fixed number of leaves receive the smallest and largest ranks under a bijective mapping to the positive integers. It establishes the result separately for strictly k-furcating trees, where every internal node has exactly k descendants, and for at-most-k-furcating trees, where internal nodes have between 2 and k descendants. A sympathetic reader would care because the induced numerical order lets tree shape be treated as a quantity, supporting direct measurement of balance in phylogenetic data. The work supplies recurrences for the extremal ranks together with their leading asymptotic growth.

Core claim

In the bijective ranking scheme, for trees on a fixed number of leaves the maximally balanced tree receives the minimal rank and the minimally balanced tree receives the maximal rank. The identification holds in both the strictly k-furcating and at-most-k-furcating settings. Recurrences are derived for the maximal and minimal ranks, and the maximal rank on (n-1)(k-1)+1 leaves in the strict case grows as (k!)^{1/(k-1)} beta_k raised to k^n, while the at-most-k case on n leaves grows as (k!)^{1/(k-1)} gamma_k raised to k^n, with beta_k decreasing in k and gamma_k greater than beta_k for k at least 3.

What carries the argument

The bijective encoding that assigns each unlabeled multifurcating rooted tree a unique positive integer, generalizing an earlier scheme for bifurcating trees.

If this is right

  • Recurrences permit direct computation of the extremal ranks for any given leaf count.
  • The maximal rank admits an explicit leading asymptotic form involving the constants beta_k and gamma_k.
  • beta_k decreases as k increases.
  • gamma_k exceeds beta_k whenever k is at least 3.

Where Pith is reading between the lines

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

  • The numerical ranks could be used to compare the shapes of empirical phylogenies without generating the full set of possible trees.
  • The balance-to-rank correspondence may hold for other combinatorial numberings of trees beyond the one studied here.
  • Rapid growth of the rank range with leaf number implies that sampling methods based on the encoding must account for an exponentially widening spread.

Load-bearing premise

The bijective ranking scheme orders trees so that relative balance directly controls the numerical rank for any fixed leaf count.

What would settle it

Enumerate all multifurcating trees on five or six leaves, assign their ranks under the encoding, and check whether the most balanced tree always receives the smallest integer while the least balanced receives the largest.

read the original abstract

Maranca and Rosenberg (2024) devised a ranking scheme for unlabeled multifurcating rooted trees, in which the trees are bijectively associated with the positive integers. Here, generalizing earlier results for bifurcating trees, we determine, for trees with a fixed number of leaves, which multifurcating trees obtain the maximal and minimal ranks. We identify these maximizing and minimizing trees for each of two sets of unlabeled multifurcating rooted trees: strictly $k$-furcating trees, in which each internal node possesses exactly $k$ descendants, and at-most-$k$-furcating trees, in which internal nodes possess at least 2 and at most $k$ descendants. In both scenarios, we find that a tree that can be regarded as maximally balanced attains the minimal rank, and a minimally balanced tree attains the maximal rank. We deduce recurrences for the maximal and minimal rank for trees with fixed numbers of leaves in both the strictly $k$-furcating and at-most-$k$-furcating cases. The maximal rank on $(n-1)(k-1)+1$ leaves grows with $(k!)^{\frac{1}{k-1}} \beta_k^{(k^n)}$ in the strictly $k$-furcating case, and the maximal rank on $n$ leaves grows with $(k!)^{\frac{1}{k-1}} \gamma_k^{(k^n)}$ in the at-most-$k$-furcating case, where $\beta_k > 1$ and $\gamma_k > 1$ are constants that depend on the value of $k$. We show that $\beta_k$ decreases as the value of $k$ increases, and that $\gamma_k > \beta_k$ for $k \geq 3$. The results contribute to the use of tree encodings for empirical characterization of phylogenies and measurement of tree balance.

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

2 major / 2 minor

Summary. The manuscript generalizes prior results on extremal ranks of bifurcating trees to unlabeled multifurcating rooted trees under the bijective positive-integer encoding of Maranca and Rosenberg (2024). For trees with a fixed number of leaves, it identifies a maximally balanced tree as attaining minimal rank and a minimally balanced tree as attaining maximal rank, in both the strictly k-furcating case (every internal node has exactly k children) and the at-most-k-furcating case (2 to k children). Recurrences are stated for the extremal ranks as functions of leaf count; asymptotic expressions are given for the maximal rank, of the form (k!)^{1/(k-1)} β_k^{(k^n)} (strictly k-furcating) and (k!)^{1/(k-1)} γ_k^{(k^n)} (at-most-k-furcating), together with the claims that β_k decreases with k and γ_k > β_k for k ≥ 3.

Significance. If the extremal identification and the recurrences hold, the work supplies concrete tools for using the integer rank as a balance measure in phylogenetic applications. The asymptotic forms and the inequalities on β_k and γ_k quantify growth-rate differences between the two multifurcating regimes; the monotonicity result on β_k is a concrete, falsifiable statement that strengthens the contribution.

major comments (2)
  1. [Abstract] Abstract and the section deriving the extremal trees: the central claim that the maximally balanced tree minimizes rank (and the minimally balanced tree maximizes it) is load-bearing for all subsequent results. The manuscript must explicitly verify that, under the recursive subtree-ordering rule of the 2024 encoding generalized to k descendants, no other tree with the same leaf count receives a strictly smaller (or larger) rank; a counter-example for any small n and k ≥ 3 would falsify both the identification and the recurrences.
  2. [Recurrence and asymptotic sections] The recurrence and asymptotic sections: the claimed recurrences for min/max rank must be shown to follow directly from the encoding’s combination rule rather than from an auxiliary assumption about balance; the passage from recurrence to the stated asymptotic form (including the explicit constants β_k and γ_k) requires a derivation that isolates the base-(k!)^{1/(k-1)} factor and proves the monotonicity β_k ↓ k.
minor comments (2)
  1. [Introduction] Notation for the two regimes (strictly k-furcating vs. at-most-k-furcating) should be introduced once with a single consistent symbol rather than repeated descriptive phrases.
  2. [Abstract] The abstract states existence of recurrences and asymptotics but supplies no small-n verification table; adding a short table of computed min/max ranks for n ≤ 10 and k = 3,4 would make the claims immediately checkable.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive major comments. We respond to each point below and will revise the manuscript to incorporate the requested clarifications and proofs.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the section deriving the extremal trees: the central claim that the maximally balanced tree minimizes rank (and the minimally balanced tree maximizes it) is load-bearing for all subsequent results. The manuscript must explicitly verify that, under the recursive subtree-ordering rule of the 2024 encoding generalized to k descendants, no other tree with the same leaf count receives a strictly smaller (or larger) rank; a counter-example for any small n and k ≥ 3 would falsify both the identification and the recurrences.

    Authors: We agree that explicit verification of the extremal identification is required. In the revision we will insert a new subsection containing an inductive proof that, under the generalized recursive ordering rule, any tree deviating from the maximally balanced structure receives a strictly larger rank (and likewise for the minimally balanced case). The base cases for small n and k=3,4 will be verified by exhaustive enumeration, and the inductive step will follow directly from the combination rule without auxiliary balance assumptions. revision: yes

  2. Referee: [Recurrence and asymptotic sections] The recurrence and asymptotic sections: the claimed recurrences for min/max rank must be shown to follow directly from the encoding’s combination rule rather than from an auxiliary assumption about balance; the passage from recurrence to the stated asymptotic form (including the explicit constants β_k and γ_k) requires a derivation that isolates the base-(k!)^{1/(k-1)} factor and proves the monotonicity β_k ↓ k.

    Authors: The recurrences are obtained by substituting the extremal subtree configurations into the encoding’s rank formula; the revision will quote the precise statement of the 2024 combination rule at each recurrence step to make the derivation self-contained. We will also expand the asymptotic section with the full derivation isolating the (k!)^{1/(k-1)} base from the product of subtree ranks when all k subtrees are identical, together with a direct comparison of the resulting sequences that establishes β_k is strictly decreasing in k. revision: yes

Circularity Check

0 steps flagged

No significant circularity; extremal identification and recurrences are derived from the encoding definition without reduction to self-referential inputs.

full rationale

The paper takes the bijective ranking from Maranca and Rosenberg (2024) as given input and derives which trees attain min/max ranks under that fixed ordering, plus the associated recurrences and asymptotics. The claim that maximally balanced trees minimize rank is presented as a proven result for the multifurcating case, not presupposed by the encoding or obtained by fitting. No equation reduces a claimed prediction to a parameter fitted from the target data, and the self-citation supplies only the foundational bijection rather than a load-bearing uniqueness theorem or ansatz that forces the extremal conclusion. The derivation chain is therefore self-contained once the encoding is accepted.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields no visible free parameters or invented entities; the central claims rest on the domain assumption of the prior bijective encoding.

axioms (1)
  • domain assumption The bijective positive-integer encoding of unlabeled multifurcating rooted trees defined in Maranca and Rosenberg (2024) extends to the strictly k-furcating and at-most-k-furcating families while preserving rank-order properties.
    All extremal characterizations and recurrences presuppose this encoding remains well-defined and bijective for the generalized tree classes.

pith-pipeline@v0.9.1-grok · 5901 in / 1320 out tokens · 51363 ms · 2026-06-30T01:02:47.708407+00:00 · methodology

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

15 extracted references

  1. [1]

    A. V. Aho and N. J. A. Sloane. Some doubly exponential sequences.Fibonacci Quarterly, 11:429—-437, 1973

    1973

  2. [2]

    P. S. Bullen.A Dictionary of Inequalities. CRC Press, Boca Raton, FL, 2nd edition, 2015

    2015

  3. [3]

    Colijn and G

    C. Colijn and G. Plazzotta. A metric on phylogenetic tree shapes.Systematic Biology, 67:113–126, 2017

    2017

  4. [4]

    Devroye, M

    L. Devroye, M. R. Doboli, N. A. Rosenberg, and S. Wagner. Tree height and the asymptotic mean of the Colijn–Plazzotta rank of unlabeled binary rooted trees.Bulletin of Mathematical Biology, 87:172, Nov. 2025

    2025

  5. [5]

    E. H. Dickey and N. A. Rosenberg. Labelled histories with multifurcation and simultaneity.Philosophical Transactions of the Royal Society of London B Biological Sciences, 380:20230307, 2025

    2025

  6. [6]

    Doboli, H.-K

    M. Doboli, H.-K. Hwang, and N. A. Rosenberg. Periodic behavior of the minimal Colijn-Plazzotta rank for trees with a fixed number of leaves. In C. Mailler and S. Wild, editors,Proceedings of the 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), volume 302, pages 18:1–18:14. Lei...

    2024

  7. [7]

    Dress, K

    A. Dress, K. T. Huber, J. Koolen, V. Moulton, and A. Spillner.Basic Phylogenetic Combinatorics. Cambridge University Press, Cambridge, 2012

    2012

  8. [8]

    B. Eldon. Evolutionary genomics of high fecundity.Annual Review of Genetics, 54:213–236, 2020

    2020

  9. [9]

    R. L. Graham, D. E. Knuth, and O. Patashnik.Concrete Mathematics. Addison-Wesley, Boston, 2nd edition, 1994

    1994

  10. [10]

    A. R. P. Maranca and N. A. Rosenberg. Bijections between the multifurcating unlabeled rooted trees and the positive integers.Advances in Applied Mathematics, 153:102612, 2024

    2024

  11. [11]

    A. Mir, A. Roger, and F. Rossell´ o. Sound Colless-like balance indices for multifurcating trees.PLoS One, 13:e0203401, 2018

    2018

  12. [12]

    N. A. Rosenberg. On the Colijn–Plazzotta numbering scheme for unlabeled binary rooted trees.Discrete Applied Mathematics, 291:88–98, 2021

    2021

  13. [13]

    Semple and M

    C. Semple and M. Steel.Phylogenetics. Oxford University Press, Oxford, 2003

    2003

  14. [14]

    J. Wirtz. On the enumeration of leaf-labeled increasing trees with arbitrary node-degree.The Art of Discrete and Applied Mathematics, 7:P1.10, 2024

    2024

  15. [15]

    Zhang and J

    J. Zhang and J. A. Palacios. Multiple merger coalescent inference of effective population size.Philosophical Transactions of the Royal Society of London B Biological Sciences, 380:20230306, 2025. 31

    2025