The distance to the border of a random tree
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929739728420864 |
|---|---|
| author | Maciá, Víctor J. |
| author_facet | Maciá, Víctor J. |
| contents | Given a Galton-Watson process conditioned to have total progeny equal to $n$, we study the asymptotic probability that this conditioned Galton-Watson process has distance to the border bigger or equal than $k$, as the number of nodes $n \rightarrow \infty$.
A problem which is akin to this one was solved by Rényi and Szekeres for Cayley trees, de Bruijn, Knuth, and Rice for plane trees and Flajolet, Gao, Odlyzko, and Richmond for binary trees. The distance to the border is dual, in a certain sense, to the height. The first of these distances is the minimum of the distances from the root to the leaves. The second is the maximum of the distances from the root to the leaves. These are two extreme complementary cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_10645 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The distance to the border of a random tree Maciá, Víctor J. Probability Combinatorics 05C05, 60J80, 32H50, 05A16 Given a Galton-Watson process conditioned to have total progeny equal to $n$, we study the asymptotic probability that this conditioned Galton-Watson process has distance to the border bigger or equal than $k$, as the number of nodes $n \rightarrow \infty$. A problem which is akin to this one was solved by Rényi and Szekeres for Cayley trees, de Bruijn, Knuth, and Rice for plane trees and Flajolet, Gao, Odlyzko, and Richmond for binary trees. The distance to the border is dual, in a certain sense, to the height. The first of these distances is the minimum of the distances from the root to the leaves. The second is the maximum of the distances from the root to the leaves. These are two extreme complementary cases. |
| title | The distance to the border of a random tree |
| topic | Probability Combinatorics 05C05, 60J80, 32H50, 05A16 |
| url | https://arxiv.org/abs/2205.10645 |