Pith. sign in

REVIEW 3 major objections 3 minor 2 cited by

An algorithm for uniform generation of unlabeled trees (P\'olya trees), with an extension of Cayley's formula

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims an efficient algorithm for uniform generation of Pólya trees based on the Burnside process, together with a product formula refining Cayley's formula.

desk verdict Solid exact sampler plus a nice Cayley refinement; the unproven mixing-time claim is the only real soft spot. read the letter →

arxiv 2411.17613 v1 pith:OKNXMVE7 submitted 2024-11-26 math.CO math.GRmath.PR

Laurent Bartholdi , Persi Diaconis This is my paper · ORCID
classification math.COmath.GRmath.PR MSC 05C0505A1560J1068W20
keywords PólyatreesuniformrandomgenerationBurnsideprocessCayley'sformulaPrüfercodesunlabeledMarkovchainMonteCarloautomorphismgroup
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper presents an efficient Monte Carlo method for drawing a uniformly random Pólya tree, a rooted unlabeled tree on $n$ vertices, by running the Burnside process, a Markov chain whose stationary distribution is uniform over the orbits of the symmetric group acting on labeled rooted trees. The two moves of the chain reduce to practical subroutines: sampling a uniform automorphism of a labeled tree, and sampling a labeled tree fixed by a given permutation. The second subroutine is solved with a new generalized Prüfer code, which also yields a closed product formula for the number of rooted labeled trees fixed by a permutation, refining Cayley's formula $n^{n-2}$. The authors observe that about 20 steps of the chain produce samples that appear uniform even for $n$ around $10^7$, and they use the sampler to compare labeled and unlabeled tree statistics against asymptotic predictions.

What carries the argument

The machinery is the Burnside process, a Markov chain alternating between picking a random automorphism of the current labeled tree and picking a uniformly random tree fixed by that permutation, whose stationary distribution is uniform over orbits, here unlabeled rooted trees. The second move is implemented by a generalized Prüfer code (Lemma 3.1, Algorithm 1) that encodes forests on $m$ vertices with an edge decoration in $[x]$ and a root decoration in $[y]$ by sequences, giving the count $(mx+y)^{m-1}y$. The tree-fixed-by-$\sigma$ construction threads these forests over each cycle length $d$, attaching $d$-fold cables to vertices of the already-built quotient tree; the divisibility condition on cycle lengths determines where cables may be attached. The first move is implemented via the automorphism partition computed in linear time using the canonical i-number labeling of rooted trees, which yields a uniform random element of the automorphism group.

What would settle it

Run the chain for 20 steps from the height-$1$ tree at $n=10^6$ and compare the empirical height, width, and degree distributions against the same statistics from a run of $10,000$ steps (allowing much longer convergence); any statistically significant gap would disprove the constant-mixing observation. Alternatively, compare the 20-step distribution of the root degree against its exact stationary value, computable from the known Pólya counts, for $n$ up to a few hundred.

Watch

Extended reading notes

Core claim

The central claim is that the Burnside process, implemented with two efficient moves, samples Pólya trees from the uniform distribution, and that the number of rooted labeled trees on $[n]$ fixed by a permutation $\sigma$ with $\lambda_d$ cycles of length $d$ is $\lambda_1^{\lambda_1-2} \prod_{d\geq 2, \lambda_d\neq 0} (d\lambda_d + \mu_d)^{\lambda_d-1} \mu_d$, where $\mu_d = \sum_{e|d,\, e<d} e\lambda_e$ and $f(m,x,y) = (mx+y)^{m-1}y$. For $\sigma = \mathrm{id}$ this reduces to $n^{n-2}$. The formula is obtained by a bijective encoding of $\sigma$-invariant trees by `$\sigma$-Prüfer sequences`, whose blocks are restricted by divisibility of cycle lengths; each block contributes one factor of the product. The authors further report empirical stationarity after about 20 Burnside steps, with tests up to $n \approx 10^7$.

Load-bearing premise

The sampler's efficiency claim rests on an experimental observation that about 20 Burnside steps suffice for $n$ up to $10^7$, with no proof of mixing; if the chain actually mixes slowly, the algorithm still targets the uniform distribution but the promised practical speed disappears.

Editorial extensions

If this is right

  • A user can obtain fixed-size uniform samples of unlabeled rooted trees for $n$ in the millions, enabling comparison of labeled versus unlabeled tree statistics where exact enumeration is impossible.
  • The product formula generalizes Cayley's formula and gives an exact count for trees invariant under any given permutation; summing these counts over a conjugacy class via Burnside's lemma recovers the Pólya counts.
  • The sampler provides a practical way to test asymptotic predictions for heights, widths, and degree distributions against finite-$n$ reality, and the reported fits suggest that the current asymptotic constants are off at accessible sample sizes.
  • The Burnside-process template applies to any group action where both orbit-sampling moves can be implemented efficiently, so other unlabeled combinatorial classes could be sampled by the same method.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • I infer that the mixing-time observation, if it holds beyond $n \approx 10^7$, would imply that the Burnside chain on trees has a spectral gap bounded away from zero independently of $n$, a striking property shared by few natural chains; the paper offers no proof, so this is a testable conjecture.
  • The fitted scale parameter $\sigma_e \approx 1.04$ for height and width, which does not move toward the asymptotic value $1.10$ as $n$ grows to $100,000$, suggests either very slow convergence of finite-$n$ corrections or an error in the asymptotic constant; computing exact expectations for $n \le 20$ via complete enumeration would separate the two possibilities.
  • The $\sigma$-Prüfer sequence bijection could be pushed further: for any group action on a class of trees admitting a Prüfer-style encoding, the same orbit-counting product structure may yield closed formulas, for example for binary phylogenetic tree shapes where a similar product formula already exists.
  • A practical extension is that the two linear-time subroutines suggest a streaming implementation that generates a tree in $O(n)$ space and near-linear expected time, suitable for interactive exploration of very large trees.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper presents a Markov-chain Monte Carlo algorithm for uniformly sampling rooted unlabeled trees (Pólya trees) on n vertices. The chain is the Burnside process on the set of rooted labeled trees under the action of permutations fixing the root. The two algorithmic primitives are: given a labeled rooted tree, sample a uniformly random automorphism (Algorithm 2); and given a permutation, sample a uniformly random tree fixed by it (Algorithm 3), using a generalized Prüfer code. A bijective encoding of invariant trees (Proposition 3.5) yields Theorem 3.3, a product formula for the number of rooted labeled trees fixed by a permutation, which refines Cayley's n^{n-2}. The paper also reports Julia experiments comparing height, width, path length, and degree statistics of sampled Pólya trees with asymptotic predictions and with labeled trees.

Significance. If the practical efficiency claim is accepted, the paper supplies a valuable tool: exact-size uniform samples of Pólya trees in a regime where the Boltzmann sampler requires many rejections. The generalized Prüfer bijection and Theorem 3.3 are elegant and appear to be new and independently interesting; the bijective proof is convincing and is illustrated with a detailed worked example. The public availability of code and data is a clear strength, as is the explicit verification against exact counts for small n. The main caveat is that the claimed O(1) mixing time, about 20 steps independently of n, is only an empirical observation with no theoretical foundation, as the authors themselves state in Appendix B. Thus the exactness of the sampler is established, but the advertised efficiency of the algorithm is not established at the same level.

major comments (3)
  1. [Section 4.1, Observation 4.1, Appendix B] The central efficiency claim that the Burnside process mixes in about 20 steps for n up to about 10^7 rests on a single experiment started from the star tree, whose stabilizer is S_{n-1}; the first step already forces a non-identity permutation and may enter the stationary regime unusually quickly. No evidence is presented for generic or worst-case starting states, no quantitative convergence diagnostics (such as multiple starts, spectral estimates, or chi-square tests against exact small-n distributions) are given, and Appendix B explicitly disclaims any theoretical foundation. Since the title and abstract advertise an efficient algorithm, this is a load-bearing weakness. I recommend either adding a substantially more robust empirical case, proving a mixing bound for a meaningful class of starting states, or carefully revising the claims so that the exact sampler with uniform stationary distribution is presented as the proven contribution and the 20-step behavior as a heuristic.
  2. [Theorem 1.2 vs. Theorem 3.3] The statement of Theorem 1.2 in the Introduction defines μ_d = sum_{e|d} e λ_d, without the proper-divisor restriction and with the wrong subscript; as printed this makes Theorem 1.2 false and inconsistent with the correct Theorem 3.3, where μ_d = sum_{e|d, e<d} e λ_e. Since this is the paper's advertised extension of Cayley's formula, the statement should be corrected in the Introduction to match Theorem 3.3.
  3. [Sections 4.2-4.4] The comparisons with asymptotic theory are weakened by the fact that the scale parameters σ_e, τ, and c are estimated from the same data that are then used to assess the quality of the fit. For example, in Section 4.2 the statement that the optimal fitted height distribution is 'extremely good' is not a goodness-of-fit test, and the reported discrepancy between σ_e ≈ 1.04 and the theoretical σ ≈ 1.10 has no confidence interval or convergence assessment. This is directly relevant to the claim in Appendix B of a systematic departure from asymptotics. Please provide standard errors, holdout or bootstrap validation, or a formal test, or alternatively soften the conclusions to a qualitative observation.
minor comments (3)
  1. [Throughout] There are several typographical errors that should be cleaned up, including 'asmyptotics' in the Introduction, 'verdify' in the proof of Lemma 3.1, and 'iff' in Section 3.2.
  2. [Section 4.4] The text refers to 'Table 3' when the displayed degree-distribution table is not numbered, and the caption of Figure 3 says 'degree-n vertices' where it appears to mean vertices of a given small degree.
  3. [Section 4.1] The statement that the qq-plot comparison shows that 'all three samplers are either correct, or at least suffer from similar bugs' is not a validation; this sentence should be revised to report the actual comparison without the informal either/or phrasing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sampling distribution and Cayley refinement are proved from first principles; the unproven mixing-time claim is an empirical limitation, not a circular step.

full rationale

The Burnside chain's stationary distribution is proved in Section 2.5 by a direct reversibility computation, so the uniform-over-orbits claim is not imported from a citation. Algorithm 2's uniform automorphism sampling follows from the recursive description of Aut(T), and Algorithm 3's uniform fixed-tree sampling follows from the generalized Prüfer bijection in Lemma 3.1; Theorem 3.3 is proved by induction from the same bijection rather than assumed. The product formula therefore refines Cayley's count by an explicit bijective construction, not by renaming or by fitting. The fitted parameters sigma_e and c in Section 4 are explicitly labeled as fits and compared with independently computed constants, so they are not predictions forced by the sampler. Observation 4.1 and Appendix B state that the constant-time mixing claim has no theoretical foundation; an unproven performance claim is a limitation of the efficiency result, but the uniform stationary distribution remains valid. Self-citations to Burnside process literature are background only and are not load-bearing. Thus no step in the derivation chain reduces to its own inputs.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The algorithm's mathematical core is self-contained: the Burnside stationary distribution and the uniform fixed-tree sampling are proved in the text. The empirical comparison sections introduce fitted scale parameters (sigma_e, tau, c) that are not load-bearing for the algorithm. The only ad hoc assumption is the unproven O(1) mixing time, which the authors flag explicitly. No new entities are postulated.

free parameters (3)
  • height scale sigma_e = ~1.04
    Fitted to 1,000,000 sampled trees with n=1000 in Section 4.2; compared to theoretical sigma = b*sqrt(rho/2) ~ 1.1027. Used only for comparison, not in the algorithm.
  • width scale tau = not reported numerically
    Fitted in Section 4.3 to width data; compared against predicted tau = 2*b*sqrt(eta/8n). Used only for comparison.
  • maximum-degree tail constant c = ~1.8
    Fitted in Section 4.4 to the tail exp(-c*n*rho^m); theoretical value from [GS94] is c ~ 1.1103. Used only for comparison.
assumptions (4)
  • ad hoc to paper Mixing of the Burnside process in O(1) steps (about 20) at n up to 10^7
    Stated in Observation 4.1 and acknowledged as unproven in Appendix B; supports the efficiency claim.
  • domain assumption Pólya's functional equation (3) and asymptotic constants b and rho
    Used in Section 4 for comparisons and for deriving sigma = b*sqrt(rho/2); taken from cited literature with numerical refinement in Section 4.5.
  • domain assumption Colbourn-Booth linear-time automorphism partition algorithm
    Invoked in Section 3.2 (Lemma 3.4) to justify uniform automorphism sampling; implementation delegates to external package.
  • domain assumption Limit theorems for height, width, path length of random Pólya trees from [Drm09] and the CRT convergence of [HM12, PS18]
    Used in Sections 4.2-4.4 to interpret simulations; not part of the algorithm itself.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An algorithm for uniform generation of unlabeled trees (P\'olya trees), with an extension of Cayley's formula." pith.science (2026). https://pith.science/paper/OKNXMVE7

@misc{pith2026241117613,
  author       = {Pith},
  title        = {Pith review of: An algorithm for uniform generation of unlabeled trees (P\'olya trees), with an extension of Cayley's formula},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OKNXMVE7}},
  note         = {Machine review of arXiv:2411.17613}
}
abstract

P\'olya trees are rooted, unlabeled trees on $n$ vertices. This paper gives an efficient, new way to generate P\'olya trees. This allows comparing typical unlabeled and labeled tree statistics and comparing asymptotic theorems with `reality'. Along the way, we give a product formula for the number of rooted labeled trees preserved by a given automorphism; this refines Cayley's formula.

Figures

Figures reproduced from arXiv: 2411.17613 by the authors.

Figure 1
Figure 1. The 16 labeled rooted trees at 1, for n “ 4. Here and below the root vertex is indicated as solid, and non-root vertices are hollow [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. The 4 unlabeled rooted trees, for n “ 4. These are called Cayley trees in his honour. In contrast, there is no formula for rooted, unlabeled trees, called P´olya trees to remember that P´olya [P´37] (followed by Otter [Ott48]) determined their asymptotics: Date: November 26, 2024. L.B. gratefully acknowledges partial support from the ERC AdG grant 101097307. P.D. gratefully acknowledges partial support from NSF gran… view at source ↗
Figure 3
Figure 3. The distributions of degree-n vertices in a random P´olya tree, for n “ 1, . . . , 8 for some constant c « 1.1103. This immediately leads to Ppmax.deg. ď mq « bρnn ´3{2 bmρ n mn´3{2 « expp´cnρmq [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Leap generators for composition schemes

    math.CO 2026-05 unverdicted novelty 7.0 of 10

    Leap generators for supercritical composition schemes C = A ∘ B yield linear-time exact-size samplers whose output distribution on size-n objects has total variation distance (c + o(1)) n^{-1/2} from uniform.

  2. Counting the number of group orbits by marrying the Burnside process with importance sampling

    math.PR 2025-01 conditional novelty 6.0 of 10

    A new algorithm estimates orbit counts by multiplying estimates of orbit-count ratios from Burnside process samples, and estimates k(U_n(F_q)) for q=2,3 up to n=32.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · cited by 2 Pith papers

  1. [1]

    Martin, The Foata-Fuchs proof of Cayley’s formula, and 24 LAURENT BARTHOLDI AND PERSI DIACONIS its probabilistic uses , Electron

    [ABBRD`23] Louigi Addario-Berry, Arthur Blanc-Renaudie, Serte Donderwinkel, Micka¨ el Maa- zoun, and James B. Martin, The Foata-Fuchs proof of Cayley’s formula, and 24 LAURENT BARTHOLDI AND PERSI DIACONIS its probabilistic uses , Electron. Commun. Probab. 28 (2023), Paper No. 17,

    work page 2023

  2. [9]

    61 (2023), no

    [DZ23] Persi Diaconis and Chenyang Zhong, Hahn polynomials and the Burnside process , Ramanujan J. 61 (2023), no. 2, 567–595. MR 4588608 [Eva08] Steven N. Evans, Probability and real trees , Lecture Notes in Mathematics, vol. 1920, Springer, Berlin, 2008, Lectures from the 35th Summer School on Probability Theory held in Saint-Flour, July 6–23,

    work page 2023

  3. [13]

    Andersen and Persi Diaconis, Hit and run as a unifying device , J

    MR 4568938 [AD07] Hans C. Andersen and Persi Diaconis, Hit and run as a unifying device , J. Soc. Fr. Stat. & Rev. Stat. Appl. 148 (2007), no. 4, 5–28. MR 2502361 [AHU75] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesl...

    work page 2007

  4. [15]

    Graph Theory 69 (2012), no

    [PS12] Konstantinos Panagiotou and Makrand Sinha, Vertices of degree k in random un- labeled trees, J. Graph Theory 69 (2012), no. 2, 114–130. MR 2864452 [PS18] Konstantinos Panagiotou and Benedikt Stufler, Scaling limits of random P´ olya trees, Probab. Theory Related Fields 170 (2018), no. 3-4, 801–820. MR 3773800 [R´59] Alfr´ ed R´ enyi, Some remarks o...

    work page 2012

  5. [21]

    Ziegler, Proofs from The Book , sixth ed., Springer, Berlin, 2018, See corrected reprint of the 1998 original [MR1723092], Including illustrations by Karl H

    MR 4627458 [AZ18] Martin Aigner and G¨ unter M. Ziegler, Proofs from The Book , sixth ed., Springer, Berlin, 2018, See corrected reprint of the 1998 original [MR1723092], Including illustrations by Karl H. Hofmann. MR 3823190 [Bab18] L´ aszl´ o Babai, Group, graphs, algorithms: the graph isomorphism problem , Pro- ceedings of the International Congress of...

    work page 2018

  6. [131]

    MR 353410 [LG05] Jean-Fran¸cois Le Gall, Random trees and applications , Probab

    (errata insert). MR 353410 [LG05] Jean-Fran¸cois Le Gall, Random trees and applications , Probab. Surv. 2 (2005), 245–311. MR 2203728 [Lov07] L´ aszl´ o Lov´ asz, Combinatorial problems and exercises , second ed., AMS Chelsea Publishing, Providence, RI,

    work page 2005

  7. [1965]

    Colbourn and Kellogg S

    MR 209176 [CB81] Charles J. Colbourn and Kellogg S. Booth, Linear time automorphism algorithms for trees, interval graphs, and planar graphs , SIAM J. Comput. 10 (1981), no. 1, 203–225. MR 605613 [CGS94] Robin Carr, William M. Y. Goh, and Eric Schmutz, The maximum degree in a random tree and related problems, Random Structures Algorithms 5 (1994), no. 1, ...

    work page 1981

  8. [2003]

    [FFP07] Philippe Flajolet, ´Eric Fusy, and Carine Pivoteau, Boltzmann sampling of unla- belled structures , Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combi- natorics, SIAM, Philadelphia, PA, 2007, pp. 201–211. MR 2498128 [FHK`23] Mareike Fischer, Lina Herbst, Sophie Kers...

    work page 2007

Show all 15 references
  1. [2007]

    MR 2321240 [Mah92] Hosam M. Mahmoud, Evolution of random search trees , Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992, A Wiley-Interscience Publication. MR 1140708 [Mat06] Frederick A. Matsen, A Geometric Approach t...

    2006

  2. [2011]

    Kolˇ cin and Vladimir P

    MR 3444818 [Kv74] Valentin F. Kolˇ cin and Vladimir P. ˇCistjakov, Combinatorial problems of proba- bility theory, Probability theory, Mathematical statistics, Theoretical cybernetics, Vol. 11 (Russian), Itogi Nauki i Tekhniki, Vsesojuz. Inst. Nauˇ cn. i Tehn. Informacii, Mosc...

    1974

  3. [2016]

    ©2016, pp. 263–274. MR 4111281 [BM08] John Adrian Bondy and Uppaluri Siva Ramachandra Murty, Graph theory, Grad- uate Texts in Mathematics, vol. 244, Springer, New York,

    2016

  4. [2017]

    Sci., vol

    MR 3644391 GENERATING P ´OLYA TREES AND EXTENDING CAYLEY’S FORMULA 25 [Drm09] Michael Drmota, Embedded trees and the support of the ISE , Combinatorial algo- rithms, Lecture Notes in Comput. Sci., vol. 5874, Springer, Berlin, 2009, pp. 194–

    2009

  5. [2018]

    Vol. IV. Invited lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 3319–3336. MR 3966534 [BKM16] Sara C. Billey, Matjaˇ z Konvalinka, and Frederick A. Matsen, IV, On trees, tan- glegrams, and tangled chains , 28th International Conference on Formal Power Se- ries and Algeb...

    2018

  6. [2023]

    Burnside process

    [Fus16] ´Eric Fusy, On symmetries in phylogenetic trees , Electron. J. Combin. 23 (2016), no. 3, Paper 3.25, 8, Paper previously numbered as: 3.22. MR 3558062 [GJ02] Leslie Ann Goldberg and Mark Jerrum, The “Burnside process” converges slowly , Combin. Probab. Comput. 11 (2002...

    2016

  7. [2024]

    Leibniz Int

    [ASS23] Markus Anders, Pascal Schweitzer, and Julian Stieß, Engineering a preprocessor for symmetry detection , 21st International Symposium on Experimental Algorithms, LIPIcs. Leibniz Int. Proc. Inform., vol. 265, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2023, pp. Art. No. 1,

    2023

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.