The decompressed tree size of k k -ary chains

Michael Wallner · 2026

Read The decompressed tree size of k k -ary chains by Michael Wallner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-18617.txt.

Introduction

Wallner studies chains: directed graphs with one start point, one end point, and ordered branches. Their depth-first spanning tree forms a single path. Such graphs arise in tree compression, and each matches one tree whose size sets the graph's size. For a fixed branch count of at least two, he finds the mean expanded size of a random chain, which holds a stretched exponential term in the square root of its size. That finding also bears on Brauer chains of fixed length.

Catalog record

CREATORMichael Wallner
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45563
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.18617

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The decompressed tree size of k k -ary chains Michael Wallner 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\geq 2 , we compute the asymptotic expected decompressed tree size of a chain of size n n chosen uniformly at random, and we show that it contains a stretched exponential term of the form e c ​ n e^{c\,\sqrt{n}} . This result also has implications for the limit distribution of Brauer chains of fixed length. Keywords: Directed acyclic graphs, addition chains, compression algorithms, generating functions, recurrence relations, asymptotic enumeration, stretched exponential. 1 Introduction Trees are a fundamental data structure in computer science. To save memory, many effective applications store them as directed acyclic graphs (DAGs) such that repeated occurrences of the same subtrees are only stored once; see Figure 1 . This process is known as sharing or DAG compression and is used in XML documents [ 3 ] , binary decision diagrams [ 21 ] , compilers [ 8 ] , and various programming languages [ 1 ] . This gives a bijection between a tree class and a DAG class. The compression is very efficient and can be implemented in worst-case time O(n) [ 8 ] . The gain in memory has been analyzed previously [ 3 , 13 ] : A uniformly chosen simply generated tree (e.g., a binary tree) of size n has on average a compressed size (i.e., the size of the DAG) that is asymptotically equivalent to \frac{C^{\prime}\,n}{\sqrt{\log n}}, with a model-dependent constant C^{\prime} . So far, nothing was known about the reverse question: What is the average decompressed size of a compressed tree chosen uniformly at random among compressed trees of the same size? In our main result we answer this question for chains , which are the simplest non-trivial class of compressed trees defined in Section 3 . In Theorem 3.1 , we prove that the expected decompressed size of chains of size n chosen uniformly at random is asymptotically equivalent to \frac{C\,e^{c\sqrt{n}}}{n^{1/4}} for explicit constants C,c>0 . The main difficulty is that it is much more difficult to enumerate DAGs than trees. Figure 1: DAG compression: A binary tree T of size 15 on the left and its compressed representation as DAG G of compressed size 5 on the right, in which repeated occurrences of the same subtrees are factored. Thus, the decompressed tree size of G is |G|_{\mathcal{T}}=15 ; see Definitions 2.1 , 2.2 , and 2.4 . In [ 15 ] we considered the reverse question of enumerating all compressed 1 1 1 Previously, the term compacted tree was used. binary trees of compressed size n . We showed that after bounding one parameter related to the height, the associated generating functions are D-finite 2 2 2 A function is D-finite if it satisfies a linear differential equation with polynomial coefficients. . Later, in [ 11 ] we solved the counting problem of unconstrained compressed binary trees using an entirely different approach on bivariate recurrence relations. We showed that their number grows like \Theta\left(n!\,4^{n}\,e^{3a_{1}n^{1/3}}\,n^{3/4}\right) for n\to\infty , where a_{1}\approx-2.331 is the largest root of the Airy function \text{Ai}(x) of the first kind 3 3 3 The Airy function \text{Ai}(x) of the first kind is characterized by \text{Ai}^{\prime\prime}(x)=x\text{Ai}(x) and \lim_{x\to\infty}\text{Ai}(x)=0 . . Such a stretched exponential term did not appear in the bounded case, proving a phase transition between the bounded and unbounded model. Similar phenomena have recently also been shown in the number of relaxed k -ary trees [ 16 ] , minimal deterministic finite automata accepting a finite binary language [ 10 ] , Young tableaux with walls [ 2 ] , and phylogenetic tree-child networks [ 6 , 14 ] . 1.1 Main result In this paper we refine the enumeration of compressed trees and, for the first time, analyze the distribution of the decompressed sizes of compressed trees of size n chosen uniformly at random. Our main result is Theorem 3.1 , which gives the asymptotic expected decompressed size for the simplest non-trivial class of compressed trees, so-called chains defined in Section 3 . In it we show that another stretched exponential appears for chains of arbitrary fixed out-degree k\geq 2 . 1.2 Plan of the paper In Section 2 we introduce the decompression algorithm and the key concept of this paper: the decompressed tree size, which lifts a tree statistic to a DAG statistic. In Section 3 we define the DAG class of chains and state our main result about their decompression. Then, we introduce in Section 4 d -exponential generating functions, which are a natural generalization of exponential generating functions, and use them in Section 5 to prove our main result. In Section 6 we discuss and study the rich combinatorics of the binary case with links to Laguerre polynomials and permutations, explaining the remarkably simple closed forms. In Section 7 we discuss connections with addition chains. Finally, in Section 8 we present several further research directions. 2 The decompressed tree size of rooted DAGs Figure 2: A rooted ordered binary DAG G with 6 internal nodes (left) and its associated decompressed binary tree D(G) with 13 internal nodes (right). In ordered DAGs the outgoing edges have a left-to-right order. In G the internal edges are shown as solid black lines and pointers as dashed red lines. Therefore, the decompressed tree size of G is |G|_{\mathcal{T}}=13 ; see Definitions 2.1 , 2.2 , and 2.4 . The motivation for this work is to understand the compression of rooted trees. Note that after compression, the root becomes the unique source of the DAG. For this purpose we consider only such DAGs. To stress the connection with trees, we henceforth call DAGs with a unique source rooted DAGs . In the language of graph theory, this is equivalent to the existence of a unique subgraph that is an arborescence. Note that all concepts can be directly generalized to DAGs with multiple roots, at the cost of losing the connection to trees. The key concept of this paper is the decompressed size of a rooted DAG. For this purpose we now define the decompression algorithm, which associates with each rooted DAG a rooted tree. We start with a few definitions. Definition 2.1 (Parameters of rooted DAGs) . The spine of a rooted DAG G is its unique spanning tree computed in a depth-first search. The edges of the spine are referred to as internal edges and the other edges of G as external edges or pointers . The fringe subgraph of a node v\in G is the induced subgraph of all nodes that can be reached from v . Now we are ready to define the decompression operator D that assigns to each rooted DAG a rooted tree that we call its decompressed tree. Definition 2.2 (Decompressed tree) . Let G be a

Read the complete text