pith. sign in

arxiv: 2604.18617 · v1 · submitted 2026-04-16 · 🧮 math.CO · cs.DM· cs.DS

The decompressed tree size of k-ary chains

Michael Wallner This is my paper

Pith reviewed 2026-05-10 10:26 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.DS
keywords k-ary chainsdecompressed tree sizestretched exponentialtree compressionBrauer chainsasymptotic analysisDAGscombinatorial enumeration
0
0 comments X

The pith

The expected decompressed tree size of a random k-ary chain of size n includes a stretched exponential of the form e^{c sqrt n}.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

A chain is a directed acyclic graph with one source and one sink, ordered children, and a depth-first search spanning tree that is a path; such objects arise as compressed representations of k-ary trees. The decompressed tree size is the number of nodes in the fully expanded tree obtained from the chain. For any fixed out-degree k at least 2, when a chain of size n is drawn uniformly at random, the expected value of this decompressed size admits an asymptotic expansion that contains the factor e raised to c times the square root of n. The same analysis yields consequences for the limiting distributions of Brauer chains of fixed length. This growth rate quantifies the typical expansion that occurs when a compressed structure is restored to its original tree form.

Core claim

For fixed out-degree 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}. This result also has implications for the limit distribution of Brauer chains of fixed length.

What carries the argument

A k-ary chain is a DAG with one source, one sink, ordered children and a depth-first-search spanning tree that is a path; the decompressed tree size is the node count of the tree recovered by expanding all shared sub-DAGs.

If this is right

  • The typical expansion ratio from chain to tree grows faster than any polynomial in n yet slower than any exponential.
  • The asymptotic supplies a precise prediction for average memory cost when a compressed k-ary structure is restored.
  • The same generating-function or singularity-analysis techniques apply to the enumeration of Brauer chains of fixed length.
  • Most random chains of size n will have decompressed sizes concentrated around this stretched-exponential growth curve.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Compression schemes that rely on DAG sharing may still incur super-polynomial overhead in the worst typical case.
  • The sqrt(n) exponent suggests that the dominant contribution comes from a small number of long shared paths rather than from many small repetitions.
  • The same model could be used to study average-case behavior of other additive-chain or addition-chain constructions in combinatorics.

Load-bearing premise

The uniform distribution over all chains of size n models the chains that actually arise in tree-compression applications.

What would settle it

Sample many uniform random k-ary chains for successive values of n and check whether their average decompressed sizes track the predicted asymptotic that includes the factor e^{c sqrt n}.

Figures

Figures reproduced from arXiv: 2604.18617 by Michael Wallner.

Figure 1
Figure 1. 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|T = 15; see Definitions 2.1, 2.2, and 2.4. In [15] we considered the reverse question of enumerating all compressed1 binary trees of compressed size n. We showed that… view at source ↗
Figure 2
Figure 2. 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|T = 13; see Definitions 2.1, 2.2, and 2.4. polynomials and permutati… view at source ↗
Figure 3
Figure 3. Figure 3: Left: A binary chain (i.e., k = 2) with 6 internal nodes. The unique root is on the very right and the unique sink on the very left. Right: The shape of ternary chains. cardinality of this subclass grows super-exponentially in the number n of internal nodes. Second, the study of this subclass was the key in all previous papers to derive asymptotic results. Third, among all compressed trees of size n, this … view at source ↗
Figure 4
Figure 4. Figure 4: Adding a new root and k − 1 pointers (in red) to a rooted k-ary DAG R; see Lemma 4.1. Lemma 4.1 (Adding a new root). Let R be a combinatorial subclass of rooted k-ary DAGs. Let S be the combinatorial class whose elements consist of a new root node with out-degree k, with an element of R as first child, and with k − 1 pointers as children 2, . . . , k; see [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The sequence construction of repeatedly adding roots (in red) from Proposition [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Left: The class R+ obtained by adding a new pointer (red bold edge) to the root of R. Right: The class R− obtained by removing the first pointer of the root of R. Note that the resulting graphs are in general not k-ary DAGs since the root has too many or too few pointers, yet these constructions are needed in the recursive construction of Theorem 5.4. Remark 4.4 (Comparison with the binary case). The resul… view at source ↗
Figure 7
Figure 7. Figure 7: A binary chain C (top) and its decompressed tree D(C) (bottom). The decompression depths and levels from Definition 5.2 are stated on the right. Lemma 5.1 associates the red path Pv in C with the node v ∈ D(C). 5 The compression depth The key idea to prove Theorem 3.1 is to relate the nodes in the decompressed trees with a statistic in the corresponding DAGs; see [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The mapping Φ = Φ1 ◦ Φ2 ◦ Φ3 from the proof of Proposition 6.1, mapping a binary chain with 4 marked vertices to one that corresponds to a valid traversal Pv0 shown in red. By Lemma 5.1 Pv0 is in bijection with a node in D(C) at level 3, since Pv0 contains 3 pointers. Now observe that by definition of C, we have pi < vi . In order to be a valid traversal, these must additionally satisfy vi−1 ≤ pi . (3) In … view at source ↗
Figure 9
Figure 9. Figure 9: Example of all preimages of the valid traversal on the top with [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The spine with dangling pointers of a relaxed binary tree of right height at most [PITH_FULL_IMAGE:figures/full_fig_p016_10.png] view at source ↗
read the original 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 \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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript defines a k-ary chain as a DAG with one source and one sink, ordered children, and a DFS spanning tree that is a path. It claims to derive the asymptotic expected decompressed tree size for a uniformly random such chain of size n, for fixed out-degree k ≥ 2, showing that this expectation includes a stretched-exponential factor of the form e^{c √n}. The paper also discusses implications for the limit distribution of Brauer chains of fixed length.

Significance. If the claimed asymptotic holds, the result is significant for analytic combinatorics applied to tree compression structures. The stretched exponential term indicates a particular type of singularity in the associated generating functions, which is consistent with the recursive structure of these DAGs. This could have implications for understanding the efficiency of compression schemes and for the analysis of addition chains in number theory.

minor comments (2)
  1. [Abstract] The constant c in the stretched exponential e^{c √n} is not given explicitly; stating its value or how it is determined would strengthen the presentation of the main result.
  2. [Abstract] The implications for Brauer chains are stated but not elaborated; a short explanation of how the result transfers to that setting would be useful for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for reviewing our manuscript and recommending minor revision. The provided summary accurately captures our definition of k-ary chains, the asymptotic analysis of the expected decompressed tree size including the stretched-exponential factor e^{c sqrt(n)}, and the implications for Brauer chains. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via standard combinatorial enumeration

full rationale

The paper defines the combinatorial class of k-ary chains explicitly (DAG with ordered children, DFS spanning tree a path, single source/sink) and encodes its bivariate generating function via a recursive decomposition. The asymptotic for the expected decompressed tree size is obtained by singularity analysis or saddle-point methods on this generating function, yielding the stretched-exponential factor e^{c√n} as a direct consequence of the dominant singularity's nature. This is a standard, non-circular analytic step that does not reduce any prediction to a fitted input or self-referential definition. No load-bearing self-citation, uniqueness theorem imported from prior work, or ansatz smuggling is present in the central claim. The uniform random model is the explicit object of study rather than an assumption smuggled in to force the result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, invented entities, or non-standard axioms; the result presumably rests on standard analytic-combinatorics machinery such as singularity analysis or recurrence relations for counting chains.

pith-pipeline@v0.9.0 · 5412 in / 1148 out tokens · 33064 ms · 2026-05-10T10:26:24.439189+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Aho, Ravi Sethi, and Jeffrey D

    Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman.Compilers, Principles, Techniques. Addison-Wesley, Boston, 1986

    work page 1986

  2. [2]

    Young Tableaux with Periodic Walls: Counting with the Density Method.Sém

    Cyril Banderier and Michael Wallner. Young Tableaux with Periodic Walls: Counting with the Density Method.Sém. Lothar. Combin., 85B, Article 85B.47:12 pp., 2021

    work page 2021

  3. [3]

    XML compression via directed acyclic graphs.Theory of Computing Systems, 57(4):1322–1371,

    Mireille Bousquet-Mélou, Markus Lohrey, Sebastian Maneth, and Eric Noeth. XML compression via directed acyclic graphs.Theory of Computing Systems, 57(4):1322–1371,

    work page

  4. [4]

    On addition chains.Bull

    Alfred Brauer. On addition chains.Bull. Amer. Math. Soc., 45:736–739, 1939. [doi]

    work page 1939

  5. [5]

    On addition schemes

    Srećko Brlek, Pierre Castéran, and Robert Strandh. On addition schemes. InInternational Joint Conference on Theory and Practice of Software Development (TAPSOFT ’91), pages 379–393, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. [doi]

    work page 1991

  6. [6]

    Enumer- ative and distributional results ford-combining tree-child networks.Adv

    Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Michael Wallner, and Guan-Ru Yu. Enumer- ative and distributional results ford-combining tree-child networks.Adv. in Appl. Math., 157:Paper No. 102704, 58, 2024. [doi]

    work page 2024

  7. [7]

    Calculating optimal addition chains.Computing, 91(3):265–284, 2011

    Neill Michael Clift. Calculating optimal addition chains.Computing, 91(3):265–284, 2011. [doi]

    work page 2011

  8. [8]

    Downey, Ravi Sethi, and Robert Endre Tarjan

    Peter J. Downey, Ravi Sethi, and Robert Endre Tarjan. Variations on the common subexpression problem.J. Assoc. Comput. Mach., 27(4):758–771, 1980. [doi]

    work page 1980

  9. [9]

    Springer, Wien, 2009

    Michael Drmota.Random trees: an interplay between combinatorics and probability. Springer, Wien, 2009. [doi]

    work page 2009

  10. [10]

    Asymptotics of Minimal Determin- istic Finite Automata Recognizing a Finite Binary Language

    Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Asymptotics of Minimal Determin- istic Finite Automata Recognizing a Finite Binary Language. InAofA 2020, volume 159 of LIPIcs, pages 11:1–11:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. [doi]

    work page 2020

  11. [11]

    Compacted binary trees admit a stretched exponential.J

    Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Compacted binary trees admit a stretched exponential.J. Combin. Theory Ser. A, 177:Paper No. 105306, 40, 2021. [doi]. 17

    work page 2021

  12. [12]

    Cambridge University Press, Cambridge, Cambridge, 2009

    Philippe Flajolet and Robert Sedgewick.Analytic combinatorics. Cambridge University Press, Cambridge, Cambridge, 2009. [doi]

    work page 2009

  13. [13]

    Analytic variations on the common subexpression problem

    Philippe Flajolet, Paolo Sipala, and Jean-Marc Steyaert. Analytic variations on the common subexpression problem. InAutomata, languages and programming, pages 220–234. Springer, Berlin, Heidelberg, 1990. [doi]

    work page 1990

  14. [14]

    On the asymptotic growth of the number of tree-child networks.European J

    Michael Fuchs, Guan-Ru Yu, and Louxin Zhang. On the asymptotic growth of the number of tree-child networks.European J. Combin., 93:Paper No. 103278, 2021. [doi]

    work page 2021

  15. [15]

    Asymptotic enumeration of compacted binary trees of bounded right height.J

    Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner. Asymptotic enumeration of compacted binary trees of bounded right height.J. Combin. Theory Ser. A, 172:105177, 2020. [doi]

    work page 2020

  16. [16]

    Asymptotics of Relaxedk-Ary Trees

    Manosij Ghosh Dastidar and Michael Wallner. Asymptotics of Relaxedk-Ary Trees. In AofA 2024, LIPIcs, pages 15:1–15:13, Dagstuhl, Germany, 2024. Schloss Dagstuhl–Leibniz- Zentrum für Informatik. [doi]

    work page 2024

  17. [17]

    Guy.Unsolved problems in number theory

    Richard K. Guy.Unsolved problems in number theory. Problem Books in Mathematics. Springer-Verlag, New York, third edition, 2004. [doi]

    work page 2004

  18. [18]

    Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas.Probab

    Svante Janson. Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas.Probab. Surv., 4:80–145, 2007. [doi]

    work page 2007

  19. [19]

    M. Kac. A history-dependent random sequence defined by Ulam.Adv. in Appl. Math., 10(3):270–277, 1989. [doi]

    work page 1989

  20. [20]

    Knuth.The Art of Computer Programming

    Donald E. Knuth.The Art of Computer Programming. Vol. 2. Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms, Third edition

    work page 1998

  21. [21]

    Springer, Berlin Heidelberg, 1998

    Christoph Meinel and Thorsten Theobald.Algorithms and Data Structures in VLSI Design: OBDD-foundations and applications. Springer, Berlin Heidelberg, 1998. [doi]

    work page 1998

  22. [22]

    Repeated fringe subtrees in random rooted trees

    Dimbinaina Ralaivaosaona and Stephan Wagner. Repeated fringe subtrees in random rooted trees. InANALCO 2015, pages 78–88. SIAM, Philadelphia, PA, 2015. [doi]

    work page 2015

  23. [23]

    Stanley.Catalan Numbers

    Richard P. Stanley.Catalan Numbers. Cambridge University Press, New York, 2015. [doi]

    work page 2015

  24. [24]

    A bijection of plane increasing trees with relaxed binary trees of right height at most one.Theoret

    Michael Wallner. A bijection of plane increasing trees with relaxed binary trees of right height at most one.Theoret. Comput. Sci., 755:1–12, 2019. [doi]

    work page 2019

  25. [25]

    Dyck paths and inversion tables.Permutation Patterns 2023, pages 142–144, 2023

    Michael Wallner. Dyck paths and inversion tables.Permutation Patterns 2023, pages 142–144, 2023

    work page 2023

  26. [26]

    The decompressed tree size of k-ary chains

    Michael Wallner. The decompressed tree size of k-ary chains. InEuroComb’25, pages 1081–186, Budapest, 2025. HUN-REN Alfréd Rényi Institute of Mathematics. 18

    work page 2025