The Decompressed Tree Size of k-Ary Chains

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 \ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , 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}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mi>e</mml:mi> <mml:mrow> <mml:mi>c</mml:mi> <mml:mspace/> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> </mml:mrow> </mml:msup> </mml:math> . This result also has implications for the limit distribution of Brauer chains of fixed length.