Geodesic
A note on limits of sequences of binary trees
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1.

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

We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the set of possible limits and its structure as a metric space. For random trees the subtree size topology arises in the context of algorithms for searching and sorting when applied to random input, resulting in a sequence of nested trees. For these we obtain a structural result based on a local version of exchangeability. This in turn leads to a central limit theorem, with possibly mixed asymptotic normality.
DOI : 10.46298/dmtcs.10968
Classification : 05C05, 60C05, 60J10 
@article{DMTCS_2023_25_1_a14,
     author = {Gr\"ubel, Rudolf},
     title = {A note on limits of sequences of binary trees},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2023-2024},
     doi = {10.46298/dmtcs.10968},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10968/}
}
TY  - JOUR
AU  - Grübel, Rudolf
TI  - A note on limits of sequences of binary trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10968/
DO  - 10.46298/dmtcs.10968
LA  - en
ID  - DMTCS_2023_25_1_a14
ER  - 
%0 Journal Article
%A Grübel, Rudolf
%T A note on limits of sequences of binary trees
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10968/
%R 10.46298/dmtcs.10968
%G en
%F DMTCS_2023_25_1_a14
Grübel, Rudolf. A note on limits of sequences of binary trees. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 1. doi : 10.46298/dmtcs.10968. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10968/

Cité par Sources :