Coalescent random forests

DOI10.1006/JCTA.1998.2919MaRDI QIDQ1284161zbMATH OpenOpenAlexFDO

Authors Jim Pitman

Publication date 30 March 1999

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcta.1998.2919

zbMATH Keywords

clustering or coagulation processesenumerationforeststree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Review text

Suppose that rooted forests (in which the edges in each tree are directed away from the root of the tree) are formed by starting with a set of \(n\) labelled vertices and succesively adding an edge \(uv\) from a randomly chosen vertex \(u\) to the root \(v\) of a randomly chosen tree not containing \(u\). The author derives several enumeration formulae for forests and trees by means of such a coalescent construction; and he relates such a construction to models of clustering or coagulation processes with applications in various areas, among other things.

Recommendations

• scientific article; zbMATH DE number 1222135
• Random forests
• Generalized random forests
• Random recursive forests
• scientific article; zbMATH DE number 1294094
• On the asymptotics of random forests
• Random forests for genetic association studies

Cites work

• A local limit theorem for the number of nodes, the height, and the number of final leaves in a critical branching process tree
• A new proof of Cayley's formula for counting labeled trees
• A problem on random trees
• A random tree model associated with random graphs
• Arcsine Laws and Interval Partitions Derived from a Stable Subordinator
• Branching processes, random trees, and a generalized scheme of arrangements of particles
• Brownian bridge asymptotics for random mappings
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Coalescents with multiple collisions
• Component behavior near the critical point of the random graph process
• Components of Random Forests
• Construction of Markovian coalescents
• Counting forests
• Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists
• Enumerative combinatorics. Volume 2.
• Forests of labeled trees
• scientific article; zbMATH DE number 3152798 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3978019 (Why is no real title available?)
• scientific article; zbMATH DE number 3983158 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 3569817 (Why is no real title available?)
• scientific article; zbMATH DE number 3602381 (Why is no real title available?)
• scientific article; zbMATH DE number 1195781 (Why is no real title available?)
• scientific article; zbMATH DE number 3451202 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• scientific article; zbMATH DE number 3324508 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• scientific article; zbMATH DE number 3187386 (Why is no real title available?)
• LIMIT THEOREMS FOR THE NUMBER OF TREES OF A GIVEN SIZE IN A RANDOM FOREST
• On Cayley's Formula for Counting Trees
• On the number of distinct orderings of a vertex-labelled graph when rooted on different vertices
• On tree census and the giant component in sparse random graphs
• Order statistics for jumps of normalised subordinators
• Polymers and random graphs
• Probability Distributions Related to Random Mappings
• Probability on trees and networks
• Random mappings, forests, and subsets associated with Abel-Cayley-Hurwitz multinomial expansions
• Size-biased sampling of Poisson point processes and excursions
• The Asymptotic Distribution of Maximum Tree Size in a Random Forest
• The coalescent
• The continuum random tree. I
• The continuum random tree. III
• The expected linearity of a simple equivalence algorithm
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The standard additive coalescent
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator

Cited in

(43)

• Strong laws of large numbers for random forests
• The standard additive coalescent
• Forest volume decompositions and Abel-Cayley-Hurwitz multinomial expansions
• A conversation with Jim Pitman
• A bijective proof of the Shor recurrence
• Fires on trees
• Random tree-weighted graphs
• Loop-erased partitioning of a graph: mean-field analysis
• Gibbs distributions for random partitions generated by a fragmentation process
• Gromov-Hausdorff-Prokhorov convergence of vertex cut-trees of \(n\)-leaf Galton-Watson trees
• Counting trees using symmetries
• Pointed and multi-pointed partitions of type \(A\) and \(B\)
• Almost giant clusters for percolation on large trees with logarithmic heights
• Sizes of the largest clusters for supercritical percolation on random recursive trees
• A new encoding of coalescent processes: applications to the additive and multiplicative cases
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• A simple model of trees for unicellular maps
• A simple formula for the series of constellations and quasi-constellations with boundaries
• scientific article; zbMATH DE number 1195781 (Why is no real title available?)
• Random partitioning over a sparse contingency table
• scientific article; zbMATH DE number 1222135 (Why is no real title available?)
• A family of random trees with random edge lengths
• A new combinatorial representation of the additive coalescent
• A non-increasing tree growth process for recursive trees and applications
• Partition functions of discrete coalescents: from Cayley's formula to Frieze's (3) limit theorem
• Surprising identities for the greedy independent set on Cayley trees
• A recursive algorithm for trees and forests
• The fluctuations of the giant cluster for percolation on random split trees
• Asymptotics of trees with a prescribed degree sequence and applications
• Percolation on random recursive trees
• The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
• The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses
• Scaling Limits of Markov-Branching Trees and Applications
• The magical Ewens sampling formula
• Stable trees as mixings of inhomogeneous continuum random trees
• Loop-erased partitioning via parametric spanning trees: monotonicities \& 1D-scaling
• Invariance principle for fragmentation processes derived from conditioned stable Galton-Watson trees
• A Telescopic Proof of Cayley’s Formula
• Pruning, cut trees, and the reconstruction problem
• The coalescent in finite populations with arbitrary, fixed structure
• On the number of crossings in a random labeled tree
• Probabilistic enumeration and equivalence of nonisomorphic trees

This page was built for publication: Coalescent random forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1284161)