The decompressed tree size of $k$-ary chains
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910149727223808 |
|---|---|
| author | Wallner, Michael |
| author_facet | Wallner, Michael |
| contents | A chain is defined as a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree computed using a depth-first search is a path. Such DAGs emerge in the context of tree compression and are therefore uniquely associated with a tree. The tree size of a DAG is defined as the size of the associated tree. For fixed out-degree $k \geq 2$, we compute the asymptotic expected decompressed tree size of a chain of size $n$ chosen uniformly at random, and we show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. This result also has implications for the limit distribution of Brauer chains of fixed length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_18617 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The decompressed tree size of $k$-ary chains Wallner, Michael Combinatorics Discrete Mathematics Data Structures and Algorithms 05A15, 05A16, 05C05, 05C30 A chain is defined as a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree computed using a depth-first search is a path. Such DAGs emerge in the context of tree compression and are therefore uniquely associated with a tree. The tree size of a DAG is defined as the size of the associated tree. For fixed out-degree $k \geq 2$, we compute the asymptotic expected decompressed tree size of a chain of size $n$ chosen uniformly at random, and we show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. This result also has implications for the limit distribution of Brauer chains of fixed length. |
| title | The decompressed tree size of $k$-ary chains |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05A15, 05A16, 05C05, 05C30 |
| url | https://arxiv.org/abs/2604.18617 |