Samuel Regan ; Erik Slivken
-
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
-
https://doi.org/10.23638/DMTCS-21-2-1Expected size of a tree in the fixed point forestArticle
Authors: Samuel Regan ; Erik Slivken
NULL##NULL
Samuel Regan;Erik Slivken
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.
Comment: 14 pages
Volume: Vol. 21 no. 2, Permutation Patters 2018
Published on: September 27, 2019
Accepted on: September 10, 2019
Submitted on: March 30, 2019
Keywords: Mathematics - Probability, 60C05
Funding:
Source : OpenAIRE Graph- A mathematical approach to the liquid-glass transition: kinetically constrained models, cellular automata and mixed order phase transitions; Funder: European Commission; Code: 680275