Skip to content
DraconiticResearch
Search Sources API
194,226 studies31 sourcesUpdated 7 min ago
Peer-reviewedCC BYForum Math. Sigma

An algorithm for uniform generation of unlabeled (Pólya) trees

  • Laurent Bartholdi
  • Persi Diaconis
Open at sourcePDFDOICite

Abstract

Pólya trees are unlabeled rooted trees on n vertices. This paper gives a new way to generate Pólya trees, that conjecturally is very efficient. This allows comparing typical unlabeled and labeled tree statistics and comparing asymptotic theorems with “reality.” Our method is an application of the Burnside process, alternating two steps: from a labeled rooted tree, produce a uniform permutation fixing it; and from a permutation, produce a uniform labeled rooted tree fixed by it. This last step is linked to a product formula, refining Cayley’s, for the number of rooted labeled trees preserved by a given permutation.

Related

  1. Efficient sampling of the unlabeled structure of uniform random mappings and surjections
    Arnaud Carayol, Pablo Rotondo
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  2. Uniform integrability of the distance to the nearest leaf in random trees
    Víctor J. Maciá, Benedikt Stufler
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  3. On the largest common subtree of uniform attachment trees
    Johannes Bäumler, Céline Kerriou, Bas Lodewijks +4
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Product approximations for uniform spanning trees and determinantal processes
    András Mészáros, Yuval Peled
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. From second moments to pairwise negative correlation: applications to minimal and uniform spanning trees
    Pengfei Tang, Zibo Zhang
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@article{bartholdi2026algorithm,
  title = {{An algorithm for uniform generation of unlabeled (Pólya) trees}},
  author = {Laurent Bartholdi and Persi Diaconis},
  journal = {Forum Math. Sigma},
  year = {2026},
  month = nov,
  doi = {10.1017/fms.2026.10218},
  url = {https://hal.science/hal-05849739v1},
  note = {CC BY},
}
RIS
TY  - JOUR
TI  - An algorithm for uniform generation of unlabeled (Pólya) trees
AU  - Laurent Bartholdi
AU  - Persi Diaconis
PY  - 2026
DA  - 2026/11/03
JO  - Forum Math. Sigma
DO  - 10.1017/fms.2026.10218
UR  - https://hal.science/hal-05849739v1
AB  - Pólya trees are unlabeled rooted trees on n vertices. This paper gives a new way to generate Pólya trees, that conjecturally is very efficient. This allows comparing typical unlabeled and labeled tree statistics and comparing asymptotic theorems with “reality.” Our method is an application of the Burnside process, alternating two steps: from a labeled rooted tree, produce a uniform permutation fixing it; and from a permutation, produce a uniform labeled rooted tree fixed by it. This last step is linked to a product formula, refining Cayley’s, for the number of rooted labeled trees preserved by a given permutation.
ER  -