Expected size of a tree in the fixed point forest

zbMATH Open1428.60023arXiv1812.05997MaRDI QIDQ5207833FDOQ5207833

Authors: Samuel Regan, Erik Slivken 

Publication date: 13 January 2020

Abstract: We study the local limit of the fixed-point forest, a tree structure associated to a simple sorting algorithm on permutations. This local limit can be viewed as an infinite random tree that can be constructed from a Poisson point process configuration on $[0,1{]}^{m}athbbN$. We generalize this random tree, and compute the expected size and expected number of leaves of a random rooted subtree in the generalized version. We also obtain bounds on the variance of the size.

Full work available at URL: https://arxiv.org/abs/1812.05997

Recommendations

• On the maximum size of a tree in a random unlabelled unrooted forest
• Limit distributions of the maximum size of a tree in a random recursive forest
• Limit theorems on sizes of trees in a random unlabelled forest
• scientific article; zbMATH DE number 3920488
• The limit distributions of the maximum size of a tree in a random forest
• On the Number of Trees of a Given Size in a Galton--Watson Forest in the Critical Case
• The size of random fragmentation trees
• Limit theorems for the maximal tree size of a Galton-Watson forest in the critical case
• Limit distributions of the number of trees of a given size in a random forest

zbMATH Keywords

random treesPoisson point processesrandom permutationssorting algorithms

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Cited In (2)

• Will forest size structure follow the \(-2\) power-law distribution under ideal demographic equilibrium state?
• Local limit of the fixed point forest

This page was built for publication: Expected size of a tree in the fixed point forest

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