{"id":"7e7122cb-8f5e-45ec-add8-0b7d9dd5d4ca","arxiv_id":"2501.11617","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new parameter family, k-treedepth, is characterized by excluded minors T□P_l for all k-vertex trees T, unifying treedepth, the ladder theorem, and the Grid-Minor Theorem.","lead":"For every k, this paper introduces a graph parameter called k-treedepth, which interpolates between treedepth at k=1 and treewidth at large k, and proves that a graph class has bounded k-treedepth exactly when it excludes all minors of the form T□P_l for every tree T on k vertices. This unifies excluded-minor characterizations for treedepth, ladders, and grids, and yields a new strengthening of the Grid-Minor Theorem for bounded-height grids.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Induction in Theorem 29 relies on Lemma 30/Claim 30.1 with hidden dependence loops; the k-ladder extraction bound L in Claim 30.1 may be insufficient when (a)-(c) hold only in torso, not in G.","rationale":"The reader identified the Grid-Minor Theorem as the weakest assumption, which is reasonable as the largest imported black box. My stress-test instead focuses on the paper's internal induction, specifically the step in Claim 30.1 where path-partition connectivity in the torso is converted into a family of connected subgraphs of the original graph G that witness a k-ladder. That conversion is the point where the whole k-ladder exclusion hypothesis is applied, and it is the least formalized transition in the proof. If the connectedness of C'_i in G is not guaranteed, Theorem 29's inductive argument cannot get its contradiction from Lemma 16, and the main theorem would lack its core inductive engine. I found no explicit proof of this connectedness in the text; the construction and the phrase 'morally connected by (a)' (in the motivation before Claim 30.1) suggest the author is aware of the subtlety, but the formal argument is missing. The concern is concrete and testable: one can isolate the subgraph C'_i and check whether connectedness follows from the nice-pair properties (g1)-(g3), Lemma 24, and 28(d). This is not an objection to the overall strategy, only a demand for a missing verification in the central induction. Hence I keep the reader's CONDITIONAL verdict rather than strengthening it to REJECT, because the gap appears repairable and no contradiction or counterexample is evident.","tokens_in":1432,"tokens_out":1284,"duration_ms":34713,"concrete_test":"Examine the paragraph of Claim 30.1 after defining C'_i, and formally verify connectedness in G of G[Ci cup union_{B in B_i} B] for each odd i, using only (g1)-(g3) of nice pairs and 28(d), not edges of torso_G(U,B) outside G. Concretely, construct a minimal counterexample attempt: take k=2, U={a,b,c,d}, B a single bag {a,b,c,d,e} with G[B] a tree plus one missing torso-clique edge, and check whether the C'_i construction can fail connectedness in G; if it cannot fail, state the lemma 'C'_i is connected in G' and prove it from (g3). If the proof requires replacing Ci by a connected subgraph obtained from Menger paths in G[B] \\ binom{U cap B}{2}, then adjust the construction and confirm the disjointness and Lemma 16 application still go through; otherwise the induction in Theorem 29 collapses at this step.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theorem depends on the main inductive Theorem 29, whose proof rests on Claim 30.1 and Lemma 30. The load-bearing internal step is the transition from path-partition hypotheses to a k-ladder minor in Claim 30.1: after choosing L=f16(k,ell) and assuming k disjoint (V0,V2L)-paths in torso_G(U,B), the proof invokes Lemma 24 to get k disjoint paths in the original G, then builds connected subgraphs C'_1,C'_3,...,C'_{2L-1} from the path-partition condition (a) and the clique-sum bags B. It asserts these are pairwise disjoint connected subgraphs of G each intersecting every Q_j, which would contradict the exclusion of k-ladders by Lemma 16. The soft spot is that condition (a) only guarantees N_torsoG(U,B)(V_i) cap V_{i-1} is connected in torsoG(U,B)[(N_torsoG(U,B)(V_i) cap V_{i-1}) cup V_i]; the proof then takes 'Ci the vertex set of the connected component ... containing N_torsoG(U,B)(V_i) cap V_{i-1}' and defines C'_i = G[Ci cup union of B in B with B cap Ci nonempty], claiming this is connected in G. This requires that each such bag B attaches to Ci inside the same component after the clique-sums, and that different C'_i are vertex-disjoint. Disjointness holds because bags B are pairwise disjoint except through U, but connectedness of C'_i in G is not immediate from niceness alone: niceness (g3) asserts existence of disjoint paths between subsets of U cap B within G[B] minus the clique on U cap B, but the torso used in Claim 30.1 is torso_G(U,B), and the graph G containing C'_i may have additional clique-sum identifications from the construction of torso_G(U,B) that are not actually edges in G. If some needed attachment uses an edge only present in the torso and not in G, C'_i may fail to be connected in G, and Lemma 16 cannot be applied. The paper does not explicitly justify that C'_i is connected in G here; the informal phrase 'morally connected by (a)' is not a proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces k-treedepth td_k, a parameter interpolating between treedepth (k=1) and treewidth plus one (large k), defined as the largest graph parameter satisfying vertex deletion and (<k)-clique-sum axioms. The main result, Theorem 1, characterizes classes of bounded k-treedepth as exactly those excluding, for some ℓ, all minors of the form T □ P_ℓ where T ranges over trees on k vertices. This unifies the known path/treedepth and ladder/2-treedepth results and recovers the Grid-Minor Theorem in the large-k limit. The proof builds a theory of 'nice pairs' and torsos, proves a ladder-extraction lemma, constructs well-connected tree decompositions via a Bellenbaum-Diestel style potential argument, and then proves the main structural theorem by induction on adhesion. A corollary gives a qualitative strengthening of the Grid-Minor Theorem for bounded-height grids, and a companion theorem characterizes bounded k-pathdepth via bounded pathwidth plus bounded k-treedepth.","tokens_in":45816,"tokens_out":17900,"duration_ms":203093,"significance":"If the proof is correct, this is a substantial unification: it gives the first excluded-minor characterization for all k, interpolating between three central graph parameters, and it provides a new structural statement for graphs excluding rectangular grids. The paper is honest about its imported ingredients: the Grid-Minor Theorem is used as a black box, and the path decomposition lemma of Robertson-Seymour is cited with a published proof in [Erd18]. The presentation is detailed and most lemmas are proved in full. However, the current version contains a load-bearing gap in Lemma 30, where an undefined quantity t is used in the main bound, and some connectivity assertions in Claim 30.1 are only sketched. These issues are localized and likely repairable, but they prevent the central proof from being accepted as written.","major_comments":[{"comment":"The statement of Lemma 30 quantifies only over k, ℓ, c, but the proof defines f30(k, ℓ, c) using an undefined positive integer t, writing '2(k-1) + t · (f16(k, ℓ) · f9(max{k, ℓ}) + 2k)'. Later the proof asserts 'for every vertex u of G, |Π_G(W_y, u)| ≤ t since t ≥ 1 and for every connected component C of G - U, N_G(V(C)) induces a clique in torso_G(U, B), and so has size at most t'. No hypothesis in Lemma 30 bounds the size of such cliques in the torso, and the torso can have arbitrarily large cliques even when G excludes a fixed k-ladder (for instance, a star with many leaves can be turned into a torso with a large clique on U ∩ B, though that particular pair may fail niceness; the point is that no such bound is proved). This t is load-bearing: the bound in part (b) of Lemma 30 depends on it, and Lemma 30 is invoked in Claim 30.1, which is then used in the proof of Theorem 29. The lemma needs an additional parameter bounding the relevant clique/projection sizes, or a proof that such a bound follows from the exclusion of k-ladders together with niceness. Without this, the main induction of Theorem 29 does not close.","section":"Lemma 30"},{"comment":"In the case ℓ' ≥ 2L, after obtaining k disjoint (V_0, V_{2L})-paths Q_1, ..., Q_k in G via Lemma 24, the proof defines C_i as the vertex set of a connected component of the torso-induced subgraph and then asserts that N_torso(V_i) ∩ V_{i-1} is connected in G[C_i ∪ ⋃ C_i], where C_i is the family of bags B intersecting C_i. This is not immediate from the definitions: a path in the torso may use an edge of the clique on U ∩ B for some B, and while niceness gives a path in G[B] between the two endpoints, one must show that all U-vertices used by that path lie in C_i and that distinct C'_i remain vertex-disjoint. The disjointness can be justified from the path-partition property together with the fact that U ∩ B is a clique in the torso, and the connectivity can be repaired using property (g3), but neither argument appears in the manuscript. Since this step is what produces the f16(k, ℓ) pairwise disjoint connected subgraphs needed to contradict the exclusion of a k-ladder, it should be proved explicitly.","section":"Claim 30.1"},{"comment":"In the proof of Lemma 24, the text defines G′ = torso_G(V(G) \\ B, {B}). This is not the correct object: removing the whole set B also removes U ∩ B, so (U, B \\ {B}) is not a good pair in that torso. The intended definition is almost certainly G′ = torso_G(V(G) \\(B \\ U), {B}), as used in Lemma 22 and Lemma 25. The proof of Lemma 24 should be corrected accordingly.","section":"Lemma 24"}],"minor_comments":[{"comment":"In the induction step of Lemma 17, the expressions 'f17(k, ℓ)' inside the proof should be 'f17(t, ℓ)' to match the function parameter t.","section":"Lemma 17"},{"comment":"The sentence 'This implies that one the the paths in {Q_1, ..., Q_k} is disjoint from V(C)' contains a typo ('one the the' should be 'one of the').","section":"Theorem 7"},{"comment":"The threshold 'i > 3 2 (k − 1)' is a typographical artifact and should read 'i > (3/2)(k − 1)' (and similarly elsewhere). The same applies to the occurrences of '3 2 (k − 1)' in Lemma 28 and Theorem 29.","section":"Lemma 26"},{"comment":"In the proof of Lemma 33, 'for every every vertex i' is a typo, and the notation φ_i(z) in the final sequence should be checked: the indices of the moving token sequences are not always consistent with the earlier definition.","section":"Lemma 33"},{"comment":"The sentence 'Not that S C_i and S C_j are disjoint...' should read 'Note that ...'.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The paper is ambitious and the overall strategy is credible, but the undefined parameter t in Lemma 30 is a real obstacle in the central proof, not merely a presentational slip. I would like to see the authors add the missing hypothesis and adjust the subsequent recursion, and also spell out the connectivity argument in Claim 30.1. If those repairs are made cleanly, the result would be a strong contribution suitable for a leading combinatorics journal. The reliance on the Grid-Minor Theorem as a black box is acceptable given the paper's stated goal of a qualitative unification; the enormous bounds are not a defect for the stated claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Clément Rambaud's paper proves a unified excluded-minor characterization for k-treedepth, covering treedepth (k=1), ladders (k=2), and treewidth (large k). That is the real news. The k-treedepth parameter itself is new for general k, and Theorem 1 gives the if-and-only-if with T□P_l excluded for all trees on k vertices. The corollary on bounded-height grids is a nice strengthening of Grid-Minor and follows from a genuinely new part (Section 8). The paper is well above the average arXiv submission: the proofs are detailed, the hard direction is structured through explicit lemmas, and the use of the Grid-Minor Theorem as a black box is honest and clearly stated. No circularity, no fitted parameters, no invented consistency checks. I could not machine-check everything, but I read the central induction in Theorem 29 and the machinery around nice pairs, and I did not find a load-bearing gap.\n\nThe stress-test note worried about connectivity in Claim 30.1: after choosing C_i in the torso, the proof asserts N(V_i)∩V_{i-1} is connected in G[C_i ∪ union of bags]. The note suspected this uses torso edges that are not in G. On reading, the step is valid: every torso edge between vertices of U∩B is realized in G by a path inside G[B] \\ clique by condition (g3) with i=1, and those bags are included in the union. The proof is too terse here and should spell this out, but the logic works. Similarly, the disjointness of the C'_i follows from the path partition condition plus the clique property of bag intersections.\n\nThe real soft spots are minor. The abstract's statement that Theorem 1 implies the Grid-Minor Theorem 'for large values of k' is over-cooked; as the reader says, it is an asymptotic consistency statement, not a proof of Grid-Minor. That should be reworded. The bounds are astronomical because of the Grid-Minor black box and the recursive definitions; that is a caveat for applications, not a flaw. The proof of Lemma 28 is heavy, and one typo f17(k,l) appears where f17(t,l) is meant, but nothing that shakes the argument.\n\nWho should read this: structural graph theorists working on graph minors, tree decompositions, and width parameters. It will be cited. It deserves a serious referee and, after minor revisions, publication.","headline":"A genuinely new excluded-minor characterization for k-treedepth, carefully proved; the stress-test worry about Claim 30.1 does not land on close reading.","tokens_in":46468,"tokens_out":3375,"would_cite":true,"duration_ms":37098,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C83","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"A class of graphs has bounded k-treedepth iff it excludes every tree-times-path T□Pℓ minor for some ℓ.","keywords":["k-treedepth","k-pathdepth","graph minors","treewidth","treedepth","grid graph","tree decomposition","clique-sum"],"falsifier":"For $k=3$, the only tree on three vertices is the path $P_3$; a concrete falsifier would be an infinite family of graphs with unbounded $3$-treedepth in which $P_3 \\square P_2$ is never a minor. More generally, for any fixed $k$, one may search for graphs of unbounded $k$-treedepth that avoid every $T \\square P_\\ell$ minor for all trees $T$ on $k$ vertices at a single fixed $\\ell$; such a family would refute Theorem 1.","tokens_in":45196,"feed_emoji":"🌲","tokens_out":14647,"duration_ms":132430,"temperature":0.7,"pith_summary":"This paper introduces $k$-treedepth, a graph parameter that interpolates between treedepth ($k=1$) and treewidth plus one ($k$ large), and proves one excluded-minor characterization for every $k$: a class of graphs has bounded $k$-treedepth if and only if, for some fixed length $\\ell$, it contains no graph of the form $T \\square P_\\ell$ as a minor, where $T$ is any tree on $k$ vertices and $P_\\ell$ is a path. The same statement specializes to three previously separate results: paths for treedepth, ladders for $2$-treedepth, and grids for treewidth. As a corollary, every graph that avoids the $k \\times \\ell$ rectangular grid as a minor has $(2k-1)$-treedepth bounded by a function of $k$ and $\\ell$, giving a bounded-height analogue of the Grid-Minor Theorem with a cleaner obstruction. A reader should care because the theorem replaces three ad-hoc structural results with one mechanism, and it sharpens what it means to exclude a grid of bounded height.","feed_headline":"For every k, bounded k-treedepth equals excluding tree-path minors","feed_subtitle":"A single excluded-minor condition interpolates treedepth, ladders, and treewidth—and bounds height-k grids.","key_machinery":"The load-bearing objects are: $k$-dismantable tree decompositions, defined by repeatedly deleting a vertex that belongs to every bag or splitting along an adhesion of size $<k$, with $k$-treedepth equal to one plus the minimum width; $k$-ladders, graphs on $[k] \\times [\\ell]$ whose rows are paths and whose columns are connected, because a pigeonhole argument over the $k^{k-2}$ labelled trees on $k$ vertices converts a long enough $k$-ladder into a $T \\square P_\\ell$ minor; and nice pairs $(U,B)$, star-shaped decompositions of a torso in which the connectivity between subsets of $U$ inside the torso is the same as inside the original graph. The proof manufactures nice pairs from lean tree decompositions with bounded adhesion and combines them by $(<k)$-clique-sums. The Grid-Minor Theorem enters once, as a black box, to guarantee that graphs with no large $k$-ladder minor have bounded treewidth.","core_discovery":"Let $\\mathrm{td}_k$ be the largest graph invariant satisfying: $\\mathrm{td}_k(\\emptyset)=0$; deleting a vertex reduces the invariant by at most one; and a $(<k)$-clique-sum (gluing two graphs along a clique of fewer than $k$ vertices) has invariant at most the maximum of the two summands. This invariant agrees with treedepth for $k=1$, with the known $2$-treedepth for $k=2$, and with treewidth plus one for $k \\ge |V(G)|$. The paper's central claim is that bounded $k$-treedepth is equivalent to excluding $T \\square P_\\ell$ as a minor for every tree $T$ on $k$ vertices, for some fixed $\\ell$. The easy direction shows that $T \\square P_\\ell$ itself has unbounded $k$-treedepth as $\\ell$ grows. The hard direction proves that any graph avoiding all $k$-ladders of length $\\ell$ (graphs whose vertex set is $[k] \\times [\\ell]$, with each row a path and each column connected) has $k$-treedepth bounded by a function of $k$ and $\\ell$: it decomposes the graph into nice pairs using well-connected tree decompositions with adhesions below $k$, and bounds each piece recursively. Since a sufficiently long $k$-ladder contains $T \\square P_\\ell$ as a minor by a pigeonhole argument on labelled trees, the ladder-free hypothesis is exactly the right obstruction. Consequently, forbidding the $k \\times \\ell$ grid forces $(2k-1)$-treedepth to be bounded by $f(k,\\ell)$, which is the paper's strengthening of the Grid-Minor Theorem for bounded-height grids.","pith_inferences":["The proof only guarantees existence of $f(k,\\ell)$ by importing the Grid-Minor Theorem; converting this into an explicit or polynomial bound is a natural follow-up that the paper does not attempt.","The $k$-treedepth hierarchy is likely to be a tool for other minor-monotone parameters: in particular, it should bound weak coloring numbers in minor-closed classes, extending the known role of $2$-treedepth that the paper mentions.","The Section 9 framework suggests a broader program: for any parameter built from vertex additions and $(<k)$-clique-sums, the universal obstructions should again be finitely many tree-times-path graphs; testing this on elimination distance to a forest is a concrete next experiment."],"forward_implications":["For $k=1$, Theorem 1 recovers the classical characterization: a minor-closed class has bounded treedepth exactly when it excludes some path $P_\\ell$.","For $k=2$, it recovers the ladder theorem: bounded $2$-treedepth exactly when some $2 \\times \\ell$ grid is excluded.","For $k$ at least $|V(G)|$, $k$-treedepth equals treewidth plus one, so the same theorem contains the Grid-Minor Theorem.","For all $k,\\ell$, graphs excluding the $k \\times \\ell$ grid have $(2k-1)$-treedepth at most a function of $k$ and $\\ell$; this is a bounded-height strengthening of the Grid-Minor Theorem.","Bounded $k$-pathdepth is equivalent to bounded pathwidth together with bounded $k$-treedepth (Theorem 4), giving a path-decomposition analogue."],"supporting_citations":[{"why":"supplies the Grid-Minor Theorem, used as a black box to bound treewidth and to force a k×l grid minor in the obstruction arguments.","marker":"[RS86]"},{"why":"introduces 2-treedepth and proves the ladder-exclusion theorem that this paper generalizes to all k.","marker":"[HJM+21]"},{"why":"supplies the elementary path-exclusion characterization of bounded treedepth, the k=1 case.","marker":"[NOdM12]"},{"why":"provides the lean tree-decomposition theorem whose style is adapted to construct well-connected decompositions.","marker":"[Tho90]"},{"why":"gives the short proof of lean tree decompositions that the potential-function argument in Section 6 follows.","marker":"[BD02]"},{"why":"supplies the monotone-subsequence theorem used in Lemma 16 to align the k rows into a k-ladder.","marker":"[ES35]"},{"why":"provides the unpublished path-decomposition lemma used to prove the k-pathdepth characterization.","marker":"[RS]"}],"fun_headline_variants":["For every k, bounded k-treedepth iff no T□Pℓ minor for any k-vertex tree T","Bounded k-treedepth: excludes T□Pℓ for every tree T of size k","Treedepth, ladder, treewidth unified: one excluded-minor condition per k","Excluding k×ℓ grid forces bounded (2k-1)-treedepth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hard direction of Theorem 1 takes the Grid-Minor Theorem as a black box, so the proof of bounded $k$-treedepth would collapse if that theorem were removed, and the bounds it produces inherit that theorem's non-explicit estimates.","fun_headline_variants_meta":{"raw":{"variants":["For every k, bounded k-treedepth iff no T□Pℓ minor for any k-vertex tree T","Bounded k-treedepth: excludes T□Pℓ for every tree T of size k","Treedepth, ladder, treewidth unified: one excluded-minor condition per k","Excluding k×ℓ grid forces bounded (2k-1)-treedepth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002221,"raw_usage":{"total_tokens":8805,"prompt_tokens":1368,"completion_tokens":7437,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":984,"completion_tokens_details":{"reasoning_tokens":7338}},"tokens_in":984,"tokens_out":7437,"duration_ms":54939,"temperature":1.0,"reasoning_tokens":7338,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:04:14.946265+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $k=3$, the only tree on three vertices is the path $P_3$; a concrete falsifier would be an infinite family of graphs with unbounded $3$-treedepth in which $P_3 \\square P_2$ is never a minor. More generally, for any fixed $k$, one may search for graphs of unbounded $k$-treedepth that avoid every $T \\square P_\\ell$ minor for all trees $T$ on $k$ vertices at a single fixed $\\ell$; such a family would refute Theorem 1.","supporting_citations":[],"review_version":1}