Abstract 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 2 k ≥ 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 \, n e c n. This result also has implications for the limit distribution of Brauer chains of fixed length.
Michael Wallner (Sat,) studied this question.