Pith. sign in

REVIEW 4 major objections 4 minor 36 references

Supertrees

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For contiguous d-ary plane trees, the smallest tree containing every k-vertex tree has exactly $d^{k-1}+k-1$ vertices.

desk verdict Exact formula and subexponential bounds for universal plane trees are new and correct; the load-bearing 'one can check' in Prop 2.4 is a gap in exposition, not the argument, and I verified it. read the letter →

arxiv 1908.03197 v2 pith:XZRS7ZQA submitted 2019-08-08 math.CO

Colin Defant , Noah Kravitz , Ashwin Sah This is my paper · ORCID
classification math.CO MSC 05A0505C0505A16
keywords k-supertreesuniversalpermutationsrootedplanetreesd-ary[d]-treespatterncontainmentinlayeredsubexponentialbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks how many vertices a rooted plane tree needs in order to contain every rooted plane tree on $k$ vertices as a pattern. For contiguous containment in $d$-ary plane trees, the answer is exact: the minimum is $d^{k-1}+k-1$. For the other three settings, namely noncontiguous $d$-ary trees, contiguous $[d]$-trees, and noncontiguous $[d]$-trees, the paper proves upper and lower bounds that improve substantially on the trivial $d^k$ bound. In particular, both noncontiguous variants have subexponential upper bounds. A closed-form minimum for a universal-object problem is uncommon, and the bounds open a path toward the same kind of exact question in related tree families.

What carries the argument

The central objects are $d$-ary plane trees, where each vertex has $d$ ordered, possibly empty subtrees, and $[d]$-trees, where each vertex has at most $d$ ordered children. Contiguous containment means the copy is a connected induced subgraph; noncontiguous containment means the copy can be obtained through legal edge contractions. The key transfer mechanism is a map $\psi$ from binary plane trees to 231-avoiding permutations: label the vertices $1,\dots,n$ so that the postorder reading is increasing, then read the labels in in-order. A legal edge contraction in the tree corresponds to deleting exactly one entry of $\psi$, namely the lower endpoint's label for a type-1 edge and the upper endpoint's label for a type-2 edge, so noncontiguous tree containment becomes permutation pattern containment. This lets the authors import the known exact minimum length of permutations containing all layered permutations. The upper bounds come from recursive constructions built from spines and vertebrae, whose sizes are analyzed through recurrences and analytic combinatorics.

What would settle it

Take any binary plane tree with a type-2 edge whose contraction is legal, compute $\psi$ before and after contracting, and check whether $\psi(T/e)$ is exactly $\psi(T)$ with the upper endpoint's label deleted and the result normalized; a failure of this correspondence would invalidate Proposition 2.4 and remove the main noncontiguous lower bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.1: for all integers $d\ge 2$ and $k\ge 1$, the minimum number of vertices in a $d$-ary plane tree that contiguously contains every $d$-ary plane tree with $k$ vertices is exactly $d^{k-1}+k-1$. The lower bound uses the $d^{k-1}$ nonisomorphic path-shaped trees on $k$ vertices: their leaves must be mapped to pairwise distinct vertices, so the universal tree needs $d^{k-1}$ vertices at depth at least $k-1$ and one vertex on each earlier level. The upper bound is the explicit tree $\Delta_d(k)$, built by attaching perfect trees to a type-1 path. For noncontiguous $d$-ary plane trees the paper claims $\eta_d k \log_2 k(1+o(1))\le N^{\mathrm{non}}_{d\text{-ary}}(k)\le k^{\frac{1}{2}\log_2 k(1+o(1))}$, with $\eta_2=1$ and $\eta_d=1/2$ for $d\ge3$. For contiguous $[d]$-trees it claims $d^{(k-2)/d}\le N^{\mathrm{con}}_{[d]}(k)\le(\rho_d+o(1))^k$, where $\rho_d$ is a computable growth constant. For noncontiguous $[d]$-trees it claims the lower bound $\frac{\eta_d}{d}k\log_2 k(1+o(1))$ and the same subexponential upper bound.

Load-bearing premise

The lower bound for noncontiguous $d$-ary trees rests on a step in Proposition 2.4, justified in the paper only by 'one can check', that contracting a type-1 edge deletes the lower endpoint's label from the permutation $\psi(T)$ and contracting a type-2 edge deletes the upper endpoint's label.

Editorial extensions

If this is right

  • For contiguous $d$-ary containment, the exact value settles the problem: the minimum is $d^{k-1}+k-1$ for every $d\ge2$ and $k\ge1$.
  • Noncontiguous $k$-universal $d$-ary plane trees and $[d]$-trees of size $k^{\frac{1}{2}\log_2 k(1+o(1))}$ exist, so allowing edge contractions reduces the required size from exponential to subexponential.
  • Every noncontiguous $k$-universal binary plane tree has at least $(k+1)\lceil\log_2(k+1)\rceil-2^{\lceil\log_2(k+1)\rceil}+1$ vertices, and for $d\ge3$ the $d$-ary analogue is at least half that.
  • For fixed $d$, the minimum sizes of noncontiguous $d$-ary and $[d]$-supertrees differ by at most a constant factor, so the two noncontiguous problems share the same growth exponent.
  • The contiguous $[d]$-tree minimum grows exponentially with a base between $d^{1/d}$ and $\rho_d$, where $\rho_d=1+\frac{4\log d}{d}+o\!\left(\frac{\log d}{d}\right)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the exact formula suggests a general obstruction in which leaf positions of path-shaped embedded trees force distinct deep vertices, a counting argument that may yield exact minima for other ordered tree families.
  • Editorial inference: the correspondence between legal edge contractions and entry deletions in $\psi$ is a transfer principle that could be used to enumerate trees by contraction-closed pattern sets or to analyze random tree contractions.
  • Editorial inference: the gap between the $\Theta(k\log_2 k)$-type lower bound and the $k^{\frac{1}{2}\log_2 k}$ upper bound is enormous; exhaustive computation of the noncontiguous minima for small $k$ could indicate whether the true growth is quasilinear or superpolynomial.
  • Editorial inference: since the paper observes that the constructions $\Xi_d(k)$ agree for all $d\ge3$, one natural question is whether $N^{\mathrm{non}}_{[d]}(k)$ is eventually independent of $d\ge3$; the paper does not claim this.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper introduces four notions of k-universal rooted plane trees: contiguous and noncontiguous containment for d-ary plane trees and for [d]-trees. For each notion it studies the minimum number of vertices of a k-supertree. The main results are an exact formula for the contiguous d-ary case, N^con_{d-ary}(k)=d^{k-1}+k-1 (Theorem 2.1), and asymptotic bounds for the other three cases. The upper bounds come from explicit recursive constructions, and the lower bounds for the noncontiguous d-ary case pass through a bijection between binary plane trees and 231-avoiding permutations, then invoke the Albert-Engen-Pantone-Vatter theorem on universal layered permutations. The paper is clearly written and the main ideas are attractive, but several steps that are load-bearing for the stated theorems are asserted without proof.

Significance. If the gaps are filled, this is a worthwhile contribution to the growing literature on universal objects in combinatorics. The exact formula in Theorem 2.1 is a clean and nontrivial result. The explicit constructions giving subexponential upper bounds in the noncontiguous settings are also interesting, and the use of an external theorem on layered permutations is transparent and not circular. The paper contains no fitted parameters, and the main derivations are explicit and verifiable. However, the lower-bound argument for noncontiguous d-ary trees depends on an unproved contraction-to-deletion lemma, and the upper-bound recurrences are stated without derivation; these omissions currently prevent the results from being fully established.

major comments (4)
  1. [Section 1.3, displayed results (II) and (IV)] The displayed lower bounds appear to contain a factor d that is not supported by the proofs. Theorem 2.2 proves N^non_{d-ary}(k) ≥ η_d((k+1)⌈log2(k+1)⌉ − 2^{⌈log2(k+1)⌉}+1), which is asymptotically η_d k log2 k with no extra factor d. For [d]-trees, Theorem 3.5 transfers a lower bound only with an additional factor 1/d. As printed, (II) and (IV) are therefore inconsistent with the theorems; please correct the constants or supply proofs of the stronger bounds.
  2. [Section 2.2.1, Proposition 2.4] The contraction-to-deletion rule is the pivotal bridge in the lower-bound argument: it is what allows the authors to pass from legal contractions of binary plane trees to pattern containment in ψ(T), and hence to the Albert–Engen–Pantone–Vatter layered-permutation bound. The rule is asserted with “One can check,” and no traversal identity is given. The same applies to the assertion in the first part of the proposition that ψ(T) avoids 231. Please supply a complete proof, for example by induction on n using the in-order and postorder labelings, or state the exact lemma as a separate proved result. Without this, the lower bounds in (II) and (IV) are unsupported.
  3. [Section 2.2.2, Proposition 2.6] The recurrence for M_d(k) is stated without proof, yet it is the basis for the upper bound in (II) through Corollary 2.7. The construction ξ_d(k) is intricate, with overlapping parts accounted for by the Kronecker-delta term, so the recurrence is not evident from the definition. Please include a derivation, or at least a precise vertex count by the parts of ξ_d(k), so that the recurrence can be checked.
  4. [Section 3.2, Theorem 3.6 and Proposition 3.7] The proof of Theorem 3.6 is omitted with the note that it is identical to the proof of Theorem 2.5, and the size recurrence for M'_d(k) in Proposition 3.7 is also stated without proof. Since these results support the upper bound in (IV), the omissions are not merely cosmetic. Please provide the proof of Theorem 3.6, or a precise statement of the modifications required for the [d]-tree setting, and derive Proposition 3.7 from the construction of Ξ_d(k).
minor comments (4)
  1. [Section 3.2, Proposition 3.7] In the last summand of the recurrence, M_d(⌊(k+1)/4⌋) should presumably be M'_d(⌊(k+1)/4⌋), since the recurrence is for M'_d(k).
  2. [Section 2.2.2, Corollary 2.7] In the proof of the lower-bound half of the corollary, the notation N_d(k) is used where M_d(k) is meant. Also, the exponent notation k^{1/2 log2(k)} is ambiguous in plain text; please typeset it unambiguously, for example as k^{(1/2)\log_2 k}, so that the induction in the proof is checkable.
  3. [Section 1.2, legal contraction for d-ary trees] The definition of legal contraction uses min(χ(v)) and max(χ(v)), but these quantities are undefined when v is a leaf and χ(v)=∅. Please clarify that an edge whose lower endpoint is a leaf is always legal, or define the condition to make this case vacuous.
  4. [Section 2.2.1, Proposition 2.3] The inequality in Proposition 2.3 is stated as strict (>) even though the argument proves N^non_{d-ary}(k) > (1/2)N^non_{2-ary}(k) only after deriving β<2α; this is fine, but the statement could be made as ≥ for clarity since the strictness is not used later.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof chain is self-contained and the one imported external bound is independent of this paper.

full rationale

Theorem 2.1 is exact and rests on an explicit lower-bound family (d-ary paths with one child per nonleaf vertex) and an explicit tree Delta_d(k), with containment verified by exhaustive case analysis; no fitted parameter is renamed as a prediction. The noncontiguous lower bound (Theorem 2.2) reduces to an external theorem of Albert, Engen, Pantone, and Vatter on universal layered permutations; that result is not by the current authors and is used only after Proposition 2.4 supplies a bijection and pattern-preserving map from binary plane trees to 231-avoiding permutations. Proposition 2.4's contraction-to-deletion rule is asserted with 'One can check,' so it is an omitted proof rather than a circular step; the surrounding argument does not assume its conclusion. The upper bounds for noncontiguous trees are constructive and proven by induction; the recurrences for Md(k) and M'_d(k) are counted from the constructions, with proofs omitted, rather than fit to the target quantities. The [d]-tree bounds are likewise established by explicit lower-bound families, recursive universal trees Lambda_d(k), and a red/blue contraction argument relating d-ary and [d]-trees. The omissions and compressed proofs (Proposition 2.4's check, Proposition 2.6's counting proof, Theorem 3.6's omitted proof) are completeness concerns, not circularity. No step in the derivation reduces by definition to the claimed result, and self-citations occur only as background references for the standard 231-avoidance characterization. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters were fitted: the constants eta_d and rho_d are derived from recurrences and roots of explicit polynomials, not tuned to data. The paper relies on standard background in permutation patterns, analytic combinatorics, and the independent layered-permutation theorem of Albert et al. It introduces no speculative entities.

assumptions (4)
  • standard math The number of binary plane trees with n vertices is the nth Catalan number, and the labeling map psi is a bijection onto 231-avoiding permutations.
    Used in Proposition 2.4 to transfer noncontiguous tree containment to permutation pattern containment.
  • domain assumption Albert, Engen, Pantone, and Vatter's theorem: the minimum length of a permutation containing all layered permutations of length k is (k+1)ceil(log2(k+1)) - 2^{ceil(log2(k+1))} + 1.
    Imported as a black box for the lower bound in Theorem 2.2; it is an external, independent result.
  • standard math Pringsheim's theorem on generating functions with nonnegative coefficients, used to identify the radius of convergence of G_d(x).
    Used in Corollary 3.4 to derive the (rho_d + o(1))^k asymptotic for the contiguous [d]-tree upper bound.
  • domain assumption The definitions of legal contraction for d-ary and [d]-trees are the intended formalizations of noncontiguous containment.
    These are definitional choices rather than empirical facts, but the paper's main quantities depend on them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Supertrees." pith.science (2026). https://pith.science/paper/XZRS7ZQA

@misc{pith2026190803197,
  author       = {Pith},
  title        = {Pith review of: Supertrees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XZRS7ZQA}},
  note         = {Machine review of arXiv:1908.03197}
}
abstract

A $k$-universal permutation, or $k$-superpermutation, is a permutation that contains all permutations of length $k$ as patterns. The problem of finding the minimum length of a $k$-superpermutation has recently received significant attention in the field of permutation patterns. One can ask analogous questions for other classes of objects. In this paper, we study $k$-supertrees. For each $d\geq 2$, we focus on two types of rooted plane trees called $d$-ary plane trees and $[d]$-trees. Motivated by recent developments in the literature, we consider "contiguous" and "noncontiguous" notions of pattern containment for each type of tree. We obtain both upper and lower bounds on the minimum possible size of a $k$-supertree in three cases; in the fourth, we determine the minimum size exactly. One of our lower bounds makes use of a recent result of Albert, Engen, Pantone, and Vatter on $k$-universal layered permutations.

Figures

Figures reproduced from arXiv: 1908.03197 by the authors.

Figure 1
Figure 1. The tree ∆3(4) is depicted on the right. This tree contiguously contains all 3-ary plane trees on 4 vertices, three of which are shown on left. Finally, we show that ∆d(k) is in fact a k-supertree. Fix any d-ary plane tree T with k vertices. If T is not a path, then it has height at most k − 2, so it fits into one of the copies of P (d) k−2 . If T is the path whose edges are all of type 1, then we can embed T in ∆d(… view at source ↗
Figure 2
Figure 2. Transforming T into Te0 . We have used the color red to indicate the edges of the inserted copy of Jmi added in the i th step. Let T be a noncontiguous k-universal d-ary plane tree with α = Nnon d -ary(k) vertices. The tree Te obtained via the above construction is also a noncontiguous k-universal d-ary plane tree, so Te0 is a noncontiguous k-universal binary plane tree. The trees Te and Te0 have the same number of … view at source ↗
Figure 3
Figure 3. From left to right: the 3-crescent; the 3-vertebra V3, with the left, center, and right leaves labeled `, c, and r (respectively); and the 2nd 3-spine. • Obtain ξd(3) from a d-crescent by giving the leaf d children (one in each position). The construction for larger k is recursive and differs for d = 2 and d > 2. (The d = 2 construction is a slight improvement on the d > 2 construction.) If d = 2, then for k ≥ 4, we… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The trees ξ2(k) for 1 ≤ k ≤ 5, along with ξ2(9). In ξ2(4), ξ2(5), and ξ2(9), the pink edges represent the spine. The orange edges represent the copies of the previously-constructed trees that are glued to the spine, and the green edges represent the tail. Proof. Fix d.…
Figure 5
Figure 5. Figure 5: An illustration of the sequence transforming T into T 0 , where d = 3 and k = 10. We also have s0 = 2, s1 = 0, and s2 = 1. Each vertex vi , for 0 ≤ i ≤ m − 1, has at most 2 children in T 0 . When vi has exactly 2 children in T 0 , we think of the subtree containing vi+…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 33 canonical work pages

  1. [1]

    Albert, M

    M. Albert, M. Engen, J. Pantone, and V. Vatter, Universal layered permutations. Electron. J. Combin. , 25 (2018)

    work page 2018

  2. [2]

    Alon, Asymptotically optimal induced universal graphs

    N. Alon, Asymptotically optimal induced universal graphs. Geom. Funct. Anal., 27 (2017), 1–32

    work page 2017

  3. [3]

    Alstrup, H

    S. Alstrup, H. Kaplan, M. Thorup, and U. Zwick, Adjacency labeling schemes and induced-universal graphs. Proc. STOC 2015, 625–634

    work page 2015

  4. [4]

    R. A. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electron. J. Combin., 6 (1999), Note 1

    work page 1999

  5. [5]

    D. A. Ashlock and J. Tillotson, Construction of small superpermutations and minimal injective superstrings. Congr. Numer., 93 (1993), 91–98

    work page 1993

  6. [6]

    Baril, S

    J.-L. Baril, S. Kirgizov, V. Vajnovszki, Patterns in treeshelves. Discrete Math., 340 (2017), 2946–2954

    work page 2017

  7. [7]

    B´ ona,Combinatorics of permutations

    M. B´ ona,Combinatorics of permutations . CRC Press, 2012

    work page 2012

  8. [8]

    Butler, Induced-universal graphs for graphs with bounded maximum degree

    S. Butler, Induced-universal graphs for graphs with bounded maximum degree. Graphs Combin. , 25 (2009), 461–468

    work page 2009

Show all 36 references
  1. [9]

    F. R. K. Chung, Universal graphs and induced-universal graphs. J. Graph Theory, 14 (1990), 443–454

    1990

  2. [10]

    F. R. K. Chung, R. L. Graham, and J. Shearer. Universal caterpillars. J. Combin. Theory Ser. B , 31 (1981), 348–355

    1981

  3. [11]

    F. R. K. Chung and R. L. Graham, On graphs which contain all small trees. J. Combin. Theory Ser. B , 24 (1978), 14–23

    1978

  4. [12]

    F. R. K. Chung, R. L. Graham, and D. Coppersmith, On trees containing all small trees. The Theory of Applications of Graphs (ed. by G. Chartrand), John Wiley and Sons (1981), 265–272

    1981

  5. [13]

    F. R. K. Chung, R. L. Graham, and N. Pippenger, On graphs which contain all small trees II. Colloquia Mathematica Societatis J´ anos Bolyai, Keszthely, Hungary (1976), 213–223

    1976

  6. [14]

    F. R. K. Chung and R. L. Graham, On universal graphs for spanning trees. J. London Math. Soc. , 27 (1983), 203–211

    1983

  7. [15]

    Dairyko, L

    M. Dairyko, L. Pudwell, S. Tyner, and C. Wynn, Noncontiguous pattern avoidance in binary trees. Electron. J. Combin., 19 (2012), P22

    2012

  8. [16]

    Defant, Polyurethane toggles

    C. Defant, Polyurethane toggles. arXiv:1904.06283

    1904 arXiv

  9. [17]

    Defant, Postorder preimages

    C. Defant, Postorder preimages. Discrete Math. Theor. Comput. Sci. , 19; 1 (2017)

    2017

  10. [18]

    Dotsenko, Pattern avoidance in labelled trees

    V. Dotsenko, Pattern avoidance in labelled trees. S´ em. Lothar. Combin., 67 (2012), Article B67b

    2012

  11. [19]

    Engen and V

    M. Engen and V. Vatter, Containing all permutations. arXiv:1810.08252

    arXiv

  12. [20]

    Eriksson, K

    H. Eriksson, K. Eriksson, S. Linusson, and J. Wastlund, Dense packing of patterns in a permutation. Ann. Comb., 11 (2007), 459–470

    2007

  13. [21]

    Esperet, A

    L. Esperet, A. Labourel, and P. Ochem. On induced-universal graphs for the class of bounded-degree graphs. Inf. Process. Lett., 108 (2008), 255–260

    2008

  14. [22]

    Flajolet and R

    P. Flajolet and R. Sedgewick, Analytic combinatorics. Cambridge University Press, Cambridge, UK, 2009

    2009

  15. [23]

    Flajolet, P

    P. Flajolet, P. Sipala, and J.-M. Steyaert, Analytic variations on the common subexpression problem. Lecture Notes in Computer Science: Automata, Languages, and Programming , 443 (1990), 220–234

    1990

  16. [24]

    Flajolet and J.-M

    P. Flajolet and J.-M. Steyaert, Patterns and pattern-matching in trees: an analysis. Information and Control 58 (1983), 19–58

    1983

  17. [25]

    Gabriel, K

    N. Gabriel, K. Peske, L. Pudwell, and S. Tay. Pattern avoidance in ternary trees. J. Integer Seq. , 15 (2012), article 12.1.5

    2012

  18. [26]

    Goldberg and E

    M. Goldberg and E. Lifshitz, On minimal universal trees. Matematicheskie Zametki, 4 (1968), 371–380

    1968

  19. [27]

    Honner, Unscrambling the hidden secrets of superpermutations

    P. Honner, Unscrambling the hidden secrets of superpermutations. Quanta Mag. (Jan. 16, 2019)

    2019

  20. [28]

    Houston, Tackling the minimal superpermutation problem

    R. Houston, Tackling the minimal superpermutation problem. arXiv:1408.5108

    arXiv

  21. [29]

    J. R. Johnson, Universal cycles for permutations. Discrete Math., 309 (2009), 5264–5270. 22

    2009

  22. [30]

    Kitaev, Patterns in Permutations and Words

    S. Kitaev, Patterns in Permutations and Words. Monographs in Theoretical Computer Science. Springer, Hei- delberg, 2011

    2011

  23. [31]

    Linton, N

    S. Linton, N. Ruˇ skuc, V. Vatter, Permutation Patterns, London Mathematical Society Lecture Note Series, Vol

  24. [32]

    A. B. Miller, Asymptotic bounds for permutations containing many different patterns. J. Combin. Theory Ser. A, 116 (2009), 92–108

    2009

  25. [33]

    Pudwell, C

    L. Pudwell, C. Scholten, T. Schrock, and A. Serrato, Noncontiguous pattern containment in binary trees. ISRN Combinatorics vol. 2014, Article ID 316535 (2014)

    2014

  26. [34]

    Rado, Universal graphs and universal functions

    R. Rado, Universal graphs and universal functions. Acta. Arith., (1964), 331– 340

    1964

  27. [35]

    Rowland, Pattern avoidance in binary trees

    E. Rowland, Pattern avoidance in binary trees. J. Combin. Theory Ser. A , 117 (2010), 741–758. Fine Hall, 304 W ashington Rd., Princeton, NJ 08544 E-mail address: cdefant@princeton.edu Grace Hopper College, Yale University, New Haven, CT 06510, USA E-mail address: noah.kravitz...

    2010

  28. [376]

    Cambridge University Press, 2010

    2010

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.