A note on limits of sequences of binary trees
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | http://dmtcs.episciences.org/10968/pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850278338671673344 |
|---|---|
| author | Rudolf Grübel |
| author_facet | Rudolf Grübel |
| author_sort | Rudolf Grübel |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-95ac4d229ec04f02a1b4e1dcd162113f |
| institution | OA Journals |
| issn | 1365-8050 |
| language | English |
| publishDate | 2023-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj-art-95ac4d229ec04f02a1b4e1dcd162113f2025-08-20T01:49:32ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-05-01vol. 25:1Analysis of Algorithms10.46298/dmtcs.1096810968A note on limits of sequences of binary treesRudolf GrübelWe 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.http://dmtcs.episciences.org/10968/pdfmathematics - combinatoricsmathematics - probability05c05, 60c05, 68w40 |
| spellingShingle | Rudolf Grübel A note on limits of sequences of binary trees Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics mathematics - probability 05c05, 60c05, 68w40 |
| title | A note on limits of sequences of binary trees |
| title_full | A note on limits of sequences of binary trees |
| title_fullStr | A note on limits of sequences of binary trees |
| title_full_unstemmed | A note on limits of sequences of binary trees |
| title_short | A note on limits of sequences of binary trees |
| title_sort | note on limits of sequences of binary trees |
| topic | mathematics - combinatorics mathematics - probability 05c05, 60c05, 68w40 |
| url | http://dmtcs.episciences.org/10968/pdf |
| work_keys_str_mv | AT rudolfgrubel anoteonlimitsofsequencesofbinarytrees AT rudolfgrubel noteonlimitsofsequencesofbinarytrees |