Regan, Samuel and Slivken, Erik - Expected size of a tree in the fixed point forest

dmtcs:5331 - Discrete Mathematics & Theoretical Computer Science, September 27, 2019, Vol. 21 no. 2, Permutation Patters 2018
Expected size of a tree in the fixed point forest

Authors: Regan, Samuel and Slivken, Erik

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]^\mathbb{N}$. 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.


Source : oai:arXiv.org:1812.05997
Volume: Vol. 21 no. 2, Permutation Patters 2018
Published on: September 27, 2019
Submitted on: March 30, 2019
Keywords: Mathematics - Probability,60C05


Share