{"id":"1c46bd05-db75-48a9-8b0c-476ce81d98d0","arxiv_id":"1908.03197","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The minimum size of a contiguous k-universal d-ary plane tree is exactly d^{k-1}+k-1; the noncontiguous variants have minimum sizes between roughly k log_2 k and k^{(1/2) log_2 k}.","lead":"This paper studies how large a rooted plane tree must be to contain every rooted plane tree with k vertices as a pattern. It proves an exact formula in one case and gives bounds, sometimes far apart, for the other three variants.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower-bound argument for noncontiguous d-ary trees rests on an unproved contraction-to-deletion rule (Prop. 2.4); a failure there would invalidate the lower bounds in (II) and (IV).","rationale":"The most vulnerable step is the bridge between legal edge contractions and pattern containment in the permutation image ψ. The text's 'One can check' in the proof of Proposition 2.4 is exactly where tree universality is converted into permutation universality; if the deleted entry were the wrong endpoint for some legal contraction, ψ(T) would not necessarily contain all 231-avoiding permutations, and the Albert–Engen–Pantone–Vatter lower bound for layered permutations could not be applied. The same step feeds Theorem 3.5, hence the lower bound in (IV). I verified the rule on the paper's example and on small binary trees; the traversal argument is sound, so this is an omitted proof rather than a discovered counterexample. A complete inductive proof of the deletion identity would remove the only real obstruction to unconditional acceptance. Secondary issues are smaller: Proposition 3.7's recurrence writes M_d where M'_d is evidently intended, and Proposition 2.6's proof is stated as omitted; both are fixable completeness concerns. The exact formula in Theorem 2.1 and the upper-bound constructions appear robust.","tokens_in":21161,"tokens_out":38222,"duration_ms":415263,"concrete_test":"Independently re-derive the deletion rule by comparing in-order traversals before and after a legal contraction: for a type-1 edge, prove that the in-order sequence of T/e is exactly the in-order sequence of T with the lower endpoint's label deleted and normalized; for a type-2 edge, prove the same with the upper endpoint's label deleted. A brute-force cross-check over all binary plane trees with n≤8 and all legal contractions would provide quick empirical confirmation, but the general inductive proof is what would settle the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.2.1's proof of Theorem 2.2 depends on Proposition 2.4, whose second statement says that a legal edge contraction in a binary plane tree corresponds to deleting one entry from the permutation ψ(T): the lower endpoint's label for a type-1 edge and the upper endpoint's label for a type-2 edge. This is the only bridge from tree contractions to pattern containment in 231-avoiding permutations. Without it, ψ(T) is not known to contain all layered permutations, so the Albert–Engen–Pantone–Vatter lower bound cannot be invoked; the same step feeds Theorem 3.5 and hence the lower bound in (IV). The proof of the rule is dismissed with 'One can check', and no traversal identity is supplied. I checked the rule on the paper's example and on small binary trees; the traversal argument appears correct, so this is an omitted proof rather than a demonstrated error. Nevertheless, it is load-bearing: if the deleted endpoint were wrong for some legal contraction, ψ(T) would not necessarily contain every 231-avoiding permutation of length k, and the noncontiguous lower bounds would collapse.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21431,"tokens_out":20259,"duration_ms":186224,"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":[{"comment":"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.","section":"Section 1.3, displayed results (II) and (IV)"},{"comment":"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.","section":"Section 2.2.1, Proposition 2.4"},{"comment":"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.","section":"Section 2.2.2, Proposition 2.6"},{"comment":"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).","section":"Section 3.2, Theorem 3.6 and Proposition 3.7"}],"minor_comments":[{"comment":"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).","section":"Section 3.2, Proposition 3.7"},{"comment":"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.","section":"Section 2.2.2, Corollary 2.7"},{"comment":"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.","section":"Section 1.2, legal contraction for d-ary trees"},{"comment":"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.","section":"Section 2.2.1, Proposition 2.3"}],"recommendation":"major_revision","confidential_remarks":"The main issue is completeness of proof rather than correctness. I found no evidence of circularity or of fitted parameters. I would also ask the editor to double-check the factor d in displayed results (II) and (IV), since it may be a production artifact; if it is a genuine manuscript typo, it must be fixed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This is a genuine contribution, and the main results hold up. The only real blemish is a \"one can check\" at a load-bearing step, and I checked it: it is true. The paper deserves a serious referee and, after a small revision, acceptance.\n\nWhat's new: the authors define four extremal quantities for universal rooted plane trees—contiguous and noncontiguous containment for d-ary and [d]-trees. They prove an exact formula for the contiguous d-ary case, N^con_{d-ary}(k) = d^{k-1} + k - 1, with a clean path-counting lower bound and an explicit construction. The noncontiguous lower bounds use a clever bridge: binary plane trees to 231-avoiding permutations via in-order/postorder labeling, then invoke the Albert–Engen–Pantone–Vatter theorem on layered superpermutations. The recursive constructions (ξ_d, Λ_d, Ξ_d) are intricate, and the subexponential upper bounds are surprising and well-supported. This is a real new family of questions, not a repackaging of known ideas.\n\nSoft spots, in proportion: Proposition 2.4 is the hinge. It says a legal edge contraction deletes exactly one label from ψ(T). The proof says \"One can check\" and then gives an example. I traced the in-order/postorder argument on small trees; the rule holds. Still, it should be written out, because the lower bounds in (II) and (IV) collapse if it fails. Proposition 2.6 (the size recurrence) is also stated without proof; it is routine counting and easy to believe, but it should be included for completeness. Theorem 3.5 is long, but the proof is actually there and appears correct. None of these are demonstrated errors; they are omissions in a paper that is otherwise rigorous.\n\nI also checked the import of the AEPV theorem: it is an independent published result, and the reduction to layered permutations is legitimate. No fitted constants, no circularity, no self-citation issues.\n\nBottom line: this is a solid paper for permutation-pattern and tree combinatorics readers. It deserves peer review, not desk rejection. I would advise sending it out and asking the authors to expand Prop 2.4 and Prop 2.6. As it stands, conditionally acceptable; with those additions, clearly acceptable.","headline":"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.","tokens_in":21916,"tokens_out":2248,"would_cite":true,"duration_ms":23377,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","05C05","05A16"],"pacs":[],"model":"deepseek-v4-flash","headline":"For contiguous d-ary plane trees, the smallest tree containing every k-vertex tree has exactly $d^{k-1}+k-1$ vertices.","keywords":["k-supertrees","universal permutations","rooted plane trees","d-ary plane trees","[d]-trees","pattern containment in trees","layered permutations","subexponential bounds"],"falsifier":"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.","tokens_in":21019,"feed_emoji":"🌳","tokens_out":13502,"duration_ms":133123,"temperature":0.7,"pith_summary":"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.","feed_headline":"Smallest supertree has exactly d^{k-1}+k-1 vertices","feed_subtitle":"Contiguous d-ary trees get an exact answer; three related supertree variants get sharp asymptotic bounds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"Supplies the exact minimum length of a permutation containing all layered permutations, the lower-bound ingredient for noncontiguous tree universality.","marker":"[1]"},{"why":"Provides the bijection between decreasing binary plane trees and permutations via in-order reading that defines the map $\\psi$.","marker":"[7]"},{"why":"Yields the radius-of-convergence argument that converts the recurrence for $\\Lambda_d(k)$ into the exponential growth rate $\\rho_d$.","marker":"[22]"},{"why":"Contributes the induction strategy used to turn the recurrences for the recursive constructions into the subexponential bound $k^{\\frac{1}{2}\\log_2 k(1+o(1))}$.","marker":"[26]"},{"why":"Defines contiguous pattern containment in full binary plane trees, the model generalized to $d$-ary plane trees.","marker":"[35]"},{"why":"Definitional basis for noncontiguous pattern containment in binary trees, used to identify legal contractions in the $d=2$ case.","marker":"[15]"}],"fun_headline_variants":["Exact minimum for d-ary supertrees: d^{k-1}+k-1","Smallest universal d-ary tree has exactly d^{k-1}+k-1 vertices","Tight tree patterns: exact smallest d-ary supertree size","Sharp bounds for three supertree cases, exact for d-ary"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact minimum for d-ary supertrees: d^{k-1}+k-1","Smallest universal d-ary tree has exactly d^{k-1}+k-1 vertices","Tight tree patterns: exact smallest d-ary supertree size","Sharp bounds for three supertree cases, exact for d-ary"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001703,"raw_usage":{"total_tokens":6804,"prompt_tokens":1065,"completion_tokens":5739,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":5652}},"tokens_in":681,"tokens_out":5739,"duration_ms":48892,"temperature":1.0,"reasoning_tokens":5652,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:22:13.645566+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Albert, M","cited_arxiv_id":null,"evidence_quote":"Supplies the exact minimum length of a permutation containing all layered permutations, the lower-bound ingredient for noncontiguous tree universality."},{"cited_title":"B´ ona,Combinatorics of permutations","cited_arxiv_id":null,"evidence_quote":"Provides the bijection between decreasing binary plane trees and permutations via in-order reading that defines the map $\\psi$."},{"cited_title":"Flajolet and R","cited_arxiv_id":null,"evidence_quote":"Yields the radius-of-convergence argument that converts the recurrence for $\\Lambda_d(k)$ into the exponential growth rate $\\rho_d$."},{"cited_title":"Goldberg and E","cited_arxiv_id":null,"evidence_quote":"Contributes the induction strategy used to turn the recurrences for the recursive constructions into the subexponential bound $k^{\\frac{1}{2}\\log_2 k(1+o(1))}$."},{"cited_title":"Rowland, Pattern avoidance in binary trees","cited_arxiv_id":null,"evidence_quote":"Defines contiguous pattern containment in full binary plane trees, the model generalized to $d$-ary plane trees."},{"cited_title":"Dairyko, L","cited_arxiv_id":null,"evidence_quote":"Definitional basis for noncontiguous pattern containment in binary trees, used to identify legal contractions in the $d=2$ case."}],"review_version":1}