{"id":"arxiv/2604.18617","url":"https://arxiv.org/abs/2604.18617","tags":["math.CO","cs.DM","cs.DS"],"score":0,"title":"The decompressed tree size of $k$-ary chains","domain":"math.CO","source":"arxiv","authors":["Michael Wallner"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-16","reactions":{}}