Geodesic
Expected size of a tree in the fixed point forest
Discrete mathematics & theoretical computer science, Permutation Patters 2018, Tome 21 (2019) no. 2

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_2_a0,
     author = {Regan, Samuel and Slivken, Erik},
     title = {Expected size of a tree in the fixed point forest},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2019},
     doi = {10.23638/DMTCS-21-2-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-2-1/}
}
TY  - JOUR
AU  - Regan, Samuel
AU  - Slivken, Erik
TI  - Expected size of a tree in the fixed point forest
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-2-1/
DO  - 10.23638/DMTCS-21-2-1
LA  - en
ID  - DMTCS_2019_21_2_a0
ER  - 
%0 Journal Article
%A Regan, Samuel
%A Slivken, Erik
%T Expected size of a tree in the fixed point forest
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-2-1/
%R 10.23638/DMTCS-21-2-1
%G en
%F DMTCS_2019_21_2_a0
Regan, Samuel; Slivken, Erik. Expected size of a tree in the fixed point forest. Discrete mathematics & theoretical computer science, Permutation Patters 2018, Tome 21 (2019) no. 2. doi: 10.23638/DMTCS-21-2-1

Cité par Sources :