{"id":"36381e92-cee3-4f83-82fe-0d76badb8c00","arxiv_id":"2608.12723","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every connected graph of tree-depth h admits a tree-partition of width at most max(1, (4h-10)Δ+1) whose indexing tree has radius at most h-1.","lead":"This paper proves that every connected graph with tree-depth h can be split into small pieces arranged like a shallow family tree, with piece size bounded by roughly 4h times the maximum degree. It is the tree-depth counterpart of a recent pathwidth theorem, and it also shows that the bound must depend on the maximum degree.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof is correct, but Claim 3's equality B'_t∩V(F_ai)=S_t∩V(F_ai) is asserted without justification and is load-bearing for the invariant; Observation 2.1 is likewise unproved.","rationale":"I stress-tested the central claim of Theorem 1.3 by checking each step of the recursive construction. Lemma 2.2 is correct: the deepest-vertex choice ensures the child subtrees of the removed vertex have at most ℓ elements of S, the induction is sound, and the bound |X|≤|S|/(ℓ+1) is exact. The path-length bound in Claim 1 is protected by Lemma 2.2(a): if x∈X_t is a leaf, then |S_t∩V(F_x)|≥ℓ+1 forces x∈S_t and ℓ=0, so x is excluded from the count; all other vertices on the x–a_t path are non-leaves and hence have depth at most h−1, giving at most h−2 vertices outside S_t∪{a_t}. The algebra for f_h(ℓ) checks out, and ℓ=h−3 yields |B'_t|≤(4h−10)Δ+1. Claim 2 is valid because components have no edges to each other and no vertex of C_i lies in S_t, so all external neighbors are in B'_t. Claim 3 is the most delicate point: the equality B'_t∩V(F_ai)=S_t∩V(F_ai) is stated as 'it follows' but actually needs the observation that no x∈X_t can be a descendant of a_i, since otherwise a_i∈\\hat{X}_t∩B_t⊆B'_t, contradicting a_i∈V(C_i). Once this is supplied, the bound |N_G(V(C_i))|≤h−2+ℓ follows from |Anc_F(ai)|≤h−2 (a_i non-leaf) and |S_t∩V(C)|≤ℓ. The radius argument is sound: each edge of T away from r strictly increases the F-depth of the associated a-vertex, so T-depth is at most h−1. The lower bound example for tree-depth 3 is correct. I found no counterexample to the theorem and no internal inconsistency. The only real issues are expository: Observation 2.1 is used everywhere but left unproved, and Claim 3's key equality lacks its one-line justification. These do not threaten the central claim, but they justify the reader's CONDITIONAL verdict; no change to that verdict is needed.","tokens_in":5841,"tokens_out":26082,"duration_ms":281510,"concrete_test":"Insert the missing proofs and re-verify Claim 3. Specifically: (1) Prove Observation 2.1 by taking a vertex of minimum depth in H and noting that any H-edge joins an ancestor-descendant pair, so a shortest path from a to any other vertex cannot leave the subtree rooted at a; uniqueness follows from depth-minimality. (2) In Claim 3, add the sentence: 'If some x∈X_t were a descendant of a_i, then the path xF a_t would contain a_i, so a_i∈\\hat{X}_t, and since a_i∈B_t, (3.3) would imply a_i∈B'_t, contradicting a_i∈V(C_i). Hence \\hat{X}_t∩V(F_ai)=∅, and therefore B'_t∩V(F_ai)=S_t∩V(F_ai).' Then confirm the resulting bound |N_G(V(C_i))|≤|Anc_F(ai)|+|S_t∩V(C)|≤(h−2)+ℓ still follows, so invariant (iii) is preserved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The recursive construction’s invariant (iii), |N_G(B_t)| ≤ h−2+ℓ, is what makes the width bound propagate. Invariant (iii) for each new large component C_i is established in Claim 3, which bounds |N_G(V(C_i))| by splitting neighbors into strict ancestors of a_i and B'_t∩V(F_ai), and then asserts the equality B'_t∩V(F_ai)=S_t∩V(F_ai). This equality is not immediate from (3.3), because B'_t also contains B_t∩\\hat{X}_t, where \\hat{X}_t is the union of all x–a_t paths for x∈X_t. The equality is nevertheless true: if some x∈X_t were a descendant of a_i, the path xF a_t would pass through a_i, so a_i∈\\hat{X}_t; since a_i∈B_t, (3.3) would force a_i∈B'_t, contradicting a_i∈V(C_i)⊆B_t\\B'_t. Hence \\hat{X}_t∩V(F_ai)=∅ and the asserted equality holds. The proof omits this one-line justification, so as written the step reads as a gap. Separately, Observation 2.1, used to select a_t at every recursion step, is labeled 'obvious' and never proved; it is true by choosing a vertex of minimum F-depth in H, but the proof should be supplied. Neither issue changes the correctness of Theorem 1.3, but both should be spelled out for a fully rigorous proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an analogue of Wood's pathwidth tree-partition theorem for tree-depth. Theorem 1.3 states that every connected graph G with tree-depth h admits a T-partition of width at most max{1, (4h-10)Δ(G)+1} for some tree T with radius at most h-1. The proof is inductive: a large bag B_t is split via a separator set X_t obtained from Lemma 2.2, the central part B'_t is shown to be small by Claim 1, and the remaining components inherit the invariants through Claim 3. A short example (Lemma 3.1) shows that the dependence on Δ(G) is necessary even for graphs of tree-depth 3.","tokens_in":6162,"tokens_out":19707,"duration_ms":234548,"significance":"The result is a natural and clean extension of Wood's recent pathwidth tree-partition theorem to the stronger parameter tree-depth, with the expected linear bound O(h Δ(G)) and a radius bound of at most h-1. The proof is essentially self-contained: Lemma 2.2 is proved in the paper, the constants are explicit and not fitted, and the lower-bound example is elementary. If the two missing justifications noted in the major comments are supplied, the theorem is correct and constitutes a solid contribution to the structural study of tree-partitions.","major_comments":[{"comment":"The equality B'_t ∩ V(F_{a_i}) = S_t ∩ V(F_{a_i}) is asserted without proof and is not immediate from (3.3), because B'_t also contains B_t ∩ X_hat_t. This equality is load-bearing: it is what turns |S_t ∩ V(C)| ≤ ℓ into |N_G(V(C_i))| ≤ h-2+ℓ, thereby maintaining invariant (iii). Please add the missing argument: since a_i ∉ X_t (otherwise a_i ∈ X_hat_t ∩ B_t ⊆ B'_t, contradicting a_i ∈ V(C_i)), the subtree F_{a_i} is disjoint from X_t. If some vertex y ∈ B_t ∩ X_hat_t ∩ V(F_{a_i}) existed, then for some x ∈ X_t the path xF a_t would meet V(F_{a_i}); because x ∉ V(F_{a_i}), the path would have to pass through a_i, forcing a_i ∈ X_hat_t ∩ B_t ⊆ B'_t, again a contradiction. Thus the equality holds, but it must be stated and proved.","section":"3, Claim 3"},{"comment":"The assertion that the minimum-depth vertex a_i ∈ V(C_i) satisfies V(C_i) ⊆ V(F_{a_i}) is stated without proof. It is true, but it requires an argument using connectedness of C_i and minimality of the depth of a_i: if some v ∈ C_i were outside F_{a_i}, a path in the connected graph G[C_i] from a_i to v would contain a first edge leaving V(F_{a_i}). Since edges of G go between ancestor and descendant in F, the endpoint outside V(F_{a_i}) would have to be a strict ancestor of a_i, contradicting the minimal depth of a_i. Please include this justification.","section":"3, before Claim 3"},{"comment":"Observation 2.1 is invoked at every recursive step to define a_t, but it is only labeled 'obvious' and no proof is supplied. Please add a proof: taking a vertex a ∈ V(H) of minimum depth in F, connectedness of H and H ⊆ clos(F) imply every vertex of H is a descendant of a; uniqueness follows because if a,b ∈ V(H) satisfy V(H) ⊆ V(F_a) ∩ V(F_b), then a is a descendant of b and b is a descendant of a, so a = b.","section":"2, Observation 2.1"}],"minor_comments":[{"comment":"Since tree-partition-width is integral, the lower bound tpw(G_n) ≥ n/2 would be more naturally stated as tpw(G_n) ≥ ⌈n/2⌉.","section":"3, Lemma 3.1"},{"comment":"The sentence 'Since F_{a_i} is contained in a component C of F_{a_t} \\ X_t' should explicitly note that this uses a_i ∉ X_t; as written the reason is implicit.","section":"3, Claim 3"}],"recommendation":"major_revision","confidential_remarks":"The proof is sound in substance and the gaps are local; I expect that adding the two missing arguments to Observation 2.1 and Claim 3 will make the paper acceptable. No new ideas or experiments are needed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Correct and clean result: the tree-depth analogue of Wood's pathwidth tree-partition theorem, proven via an original recursive separator argument. The proof is essentially sound; two small omissions should be fixed before publication.\n\nThe main theorem is new relative to the cited literature. The naive route from td(G) ≤ h goes through pathwidth and gives width O(h^2 Δ) and pw(T) ≤ 2h−1; the authors get width O(h Δ) and rad(T) ≤ h−1. The induction is carefully structured. Lemma 2.2 is a self-contained separator lemma and is proved cleanly. Claim 1's algebra checks out: the identity f_h(ℓ)−(4h−10) = ((ℓ−h+4)(ℓ−h+3))/(ℓ+1) gives the minimum at ℓ = h−3. Claim 3's neighborhood bound works, and the lower-bound example showing Δ-dependence is necessary even at tree-depth 3 is valid. There are no fitted parameters or suspect citations.\n\nThe soft spots are minor but real. Observation 2.1 is stated as obvious and used without proof; it's true (choose a vertex of minimum depth in H), but the proof is one line and should appear. More substantively, in Claim 3 the equality B′_t ∩ V(F_{ai}) = S_t ∩ V(F_{ai}) is asserted without justification. As written, this looks like a gap, because B′_t also contains B_t ∩ \\hat{X}_t and nothing in (3.3) rules out \\hat{X}_t intersecting V(F_{ai}). The equality is true: if some x ∈ X_t were in V(F_{ai}), the path x F a_t would pass through ai, putting ai in \\hat{X}_t and hence in B′_t, contradicting the fact that ai belongs to V(C_i) ⊆ B_t \\ B′_t. The paper just needs to say that. I agree with the stress-test note that this is the one load-bearing point that is skipped.\n\nNeither omission changes the correctness of Theorem 1.3. This is a solid structural result, written in a clear style, and it improves on what the pathwidth theorem would give. I'd bring it to a reading group and cite it if I were working on tree-partitions. Send it out; it deserves a serious referee. After the two small patches, it should be accepted.","headline":"Correct and clean tree-depth analogue of Wood's pathwidth tree-partition theorem, with two minor rigor gaps in the proof that are easy to patch.","tokens_in":6720,"tokens_out":3309,"would_cite":true,"duration_ms":35014,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every connected graph of tree-depth h has a tree-partition into bags of size at most (4h−10)Δ+1, arranged on a tree of radius at most h−1.","keywords":["tree-partitions","tree-depth","tree-partition-width","maximum degree","radius","pathwidth","structural graph theory"],"falsifier":"Set h=3, where the theorem predicts width at most 2Δ+1 with an indexing tree of radius at most 2. Enumerate all connected graphs on up to 12 vertices, compute tree-depth, maximum degree, and the least possible width of a T-partition over all trees T of radius at most 2; any graph with td≤3 and required width >2Δ+1 would settle the smallest open case and refute Theorem 1.3.","tokens_in":5627,"feed_emoji":"🌳","tokens_out":14063,"duration_ms":162415,"temperature":0.7,"pith_summary":"This paper proves a structural decomposition statement: every connected graph with tree-depth h can be partitioned into bags of size at most max{1,(4h−10)Δ(G)+1} indexed by a tree of radius at most h−1. In a tree-partition, vertices are grouped into bags arranged on a tree, and each edge of the graph either lies inside one bag or joins vertices in neighboring bags; tree-depth measures how tall a rooted tree is needed to realize the graph through ancestor relations. The result is the tree-depth counterpart of a recent pathwidth theorem, improving the bound for this more restrictive class from quadratic to linear in h. The proof is a recursive cutting procedure, and a closing construction shows the maximum-degree factor cannot be dropped even for tree-depth 3.","feed_headline":"Tree-depth h graphs split into bags of size at most 4hΔ","feed_subtitle":"The indexing tree has radius at most h−1, improving the pathwidth-style bound from quadratic to linear in h.","key_machinery":"The load-bearing device is Lemma 2.2, a tree-separator lemma: for a set S of vertices in a rooted tree F and any integer ℓ≥0, it produces a separator X of size at most |S|/(ℓ+1) such that every component of F\\X contains at most ℓ vertices of S, and every x∈X has at least ℓ+1 vertices of S in its subtree. In the proof this is applied with ℓ=h−3 to the set S_t of bag vertices with outside neighbors. The other central object is the anchor a_t: for every connected subgraph H of the closure of a rooted tree F, Observation 2.1 gives a unique vertex a whose subtree contains all of H, and the proof repeatedly uses the path from each separator vertex to the anchor to bound the size of the shrunken bag. The identity f_h(ℓ)−(4h−10)=(ℓ−h+4)(ℓ−h+3)/(ℓ+1) shows the chosen constant is minimal for this proof.","core_discovery":"On the paper's own terms, the central discovery is Theorem 1.3: for any connected graph G with td(G)=h, there exists a tree T with rad(T)≤h−1 and a T-partition of G whose width is at most max{1,(4h−10)Δ(G)+1}. The construction starts with one bag containing all vertices and, whenever a bag is too large, chooses a vertex a_t of the tree-depth witness F that anchors the bag, defines S_t as the vertices of the bag with neighbors outside it, and uses Lemma 2.2 to select a small set X_t of witness-tree vertices so that each component of F\\X_t contains at most h−3 vertices of S_t. The shrunken bag is then {a_t}∪S_t together with the vertices on the paths from X_t to a_t, and each remaining component becomes a new leaf-bag. The calculation f_h(ℓ)=(h−2+ℓ)(1+(h−2)/(ℓ+1))≥4h−10, minimized at ℓ=h−3, is what forces the final constant.","pith_inferences":["The constant 4h−10 is an artifact of the splitting parameter ℓ; since f_h(ℓ) has the same minimum at ℓ=h−3 and ℓ=h−4, a slightly different separator strategy could plausibly lower the constant, and the lower-bound example for h=3 is far from the upper bound.","The same 'choose anchors, cut with a tree-separator' argument should extend to other parameters defined by bounded-height closure hierarchies, such as shrub-depth or weak tree-depth, yielding similar width bounds with the height appearing linearly.","For disconnected graphs the statement would need adjustment: joining the component trees into one indexing tree naturally adds one to the radius, so the analogous theorem would likely require rad(T)≤h rather than h−1."],"forward_implications":["Every connected graph class with bounded tree-depth and bounded maximum degree has bounded tree-partition-width, with the explicit constant (4h−10)Δ+1.","Because a tree of radius h−1 has depth at most h, the indexing tree itself has bounded tree-depth, so the decomposition gives a shallow hierarchy rather than merely a tree-like one.","For graphs with td(G)≤h, the earlier pathwidth theorem would give a width bound of order h²Δ; this result reduces the dependence on h to linear, at least for connected graphs.","The recursive splitting always produces a proper subset, so the process terminates and yields the claimed bound without any further assumptions on the graph beyond connectedness and finite tree-depth."],"supporting_citations":[{"why":"Provides the pathwidth analogue whose width bound and indexing-tree objective Theorem 1.3 extends from pathwidth to tree-depth.","marker":"[13]"},{"why":"Establishes the classical theorem that tw(G) and Δ(G) bound tree-partition-width, the background form of the result.","marker":"[4]"},{"why":"Shows the classical bound is best possible up to the constant, motivating the search for near-optimal bounds.","marker":"[12]"},{"why":"Introduces tree-partitions, the central object of the paper.","marker":"[11]"}],"fun_headline_variants":["Tree-depth h graphs get tree-partitions of width O(hΔ)","Tree-depth h: bag size ≤ (4h−10)Δ+1","Shallow tree-partitions: width linear in tree-depth","Tree-depth h: T-partition with radius ≤ h−1","From pathwidth to tree-depth: better tree-partitions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the chosen cut points in the hierarchy tree are never its leaves, so each cut contributes at most h−2 extra vertices; if the only possible cut points were leaves, the claimed (4h−10)Δ+1 bound could fail.","fun_headline_variants_meta":{"raw":{"variants":["Tree-depth h graphs get tree-partitions of width O(hΔ)","Tree-depth h: bag size ≤ (4h−10)Δ+1","Shallow tree-partitions: width linear in tree-depth","Tree-depth h: T-partition with radius ≤ h−1","From pathwidth to tree-depth: better tree-partitions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001514,"raw_usage":{"total_tokens":6043,"prompt_tokens":892,"completion_tokens":5151,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":5071}},"tokens_in":508,"tokens_out":5151,"duration_ms":42001,"temperature":1.0,"reasoning_tokens":5071,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:43:52.524692+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set h=3, where the theorem predicts width at most 2Δ+1 with an indexing tree of radius at most 2. Enumerate all connected graphs on up to 12 vertices, compute tree-depth, maximum degree, and the least possible width of a T-partition over all trees T of radius at most 2; any graph with td≤3 and required width >2Δ+1 would settle the smallest open case and refute Theorem 1.3.","supporting_citations":[{"cited_title":"Tree-partitions of graphs with given pathwidth","cited_arxiv_id":"2605.27780","evidence_quote":"Provides the pathwidth analogue whose width bound and indexing-tree objective Theorem 1.3 extends from pathwidth to tree-depth."},{"cited_title":"Ding and B","cited_arxiv_id":null,"evidence_quote":"Establishes the classical theorem that tw(G) and Δ(G) bound tree-partition-width, the background form of the result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows the classical bound is best possible up to the constant, motivating the search for near-optimal bounds."},{"cited_title":"Seese, Tree-partite graphs and the complexity of algorithms, in Fundamentals of Com- putation Theory , LNCS 199, Springer, (1985), 412–421","cited_arxiv_id":null,"evidence_quote":"Introduces tree-partitions, the central object of the paper."}],"review_version":1}