{"id":"b318f335-397b-4d0d-9148-29d12f947868","arxiv_id":"2509.04026","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Every K_{1,d}-free graph that excludes the k-ladder as an induced minor has tree-independence number bounded by a function of k and d.","lead":"This paper proves that in graphs with no large induced star, forbidding a simple ladder-like graph as an induced minor forces a bounded tree-independence number, a structural parameter that controls algorithmic tractability. This is a step toward an induced version of the grid theorem and unifies several known bounded-width results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection to Theorem 1.4; the flagged length-4 assertion is sound, but the §1.1 algorithmic claim is unproved.","rationale":"The reader identified the load-bearing weakness as the assertion that each R_i has length at least 4 at the end of Theorem 6.1. On careful reading, that assertion is well-founded: the endpoint w_{i+1} belongs to Qbar^i_{t_i}, which is defined as N[R_i]\\N[S^i], so w_{i+1} has a neighbor on R_i that is not in S^i; since S^i contains all endpoints and second-endpoints of R_i, that neighbor is internal enough to force length ≥ 4. The pigeonhole argument for grouping paths by Qbar^{i-1}_j also works even with overlapping Qbar sets, since each path can be assigned to one index. I found no internal inconsistency in the main proof chain. The remaining soft spot is the Section 1.1 claim of a constructive algorithm with running time |V(G)|^{g(k,d)}. This is a stated contribution but is not proved, and no algorithmic details are provided. This justifies the reader's CONDITIONAL verdict, but not because of the identified length-4 concern. Hence I disagree with the reader's specific weakest-assumption choice while agreeing that the verdict should remain conditional. The central theorem itself appears to hold up under scrutiny.","tokens_in":26606,"tokens_out":51602,"duration_ms":444200,"concrete_test":"Verify the §1.1 algorithmic remark by extracting an explicit recursive procedure from Theorems 5.2, 6.1, and Lemma 4.3 and bounding its running time; if no such procedure with a computable g(k,d) can be extracted, delete the claim. As a secondary sanity check, re-derive the final paragraph of Theorem 6.1 to confirm that P1 is indeed induced—e.g., prove that Qbar^i ∩ Qbar^j = ∅ for all i<j (or find a small K_{1,d}-free instance where the greedy construction creates a chord in P1). A chord would invalidate the rope-ladder conclusion, but the current arguments for the nonconsecutive-step non-adjacency are terse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central mathematical claim (Theorem 1.4) appears sound. The reader's weakest assumption—that each selected R_i has length at least 4 in Theorem 6.1—is actually well-supported: because w_{i+1} ∈ Qbar^i_{t_i} = N[R_i]\\N[S^i], w_{i+1} is adjacent to a vertex of R_i that is not in S^i (i.e., not an endpoint or second-endpoint), which forces |R_i| ≥ 4. The pigeonhole step for finding ℓ paths to a single Qbar^{i-1}_j is also valid by assigning each chosen path to one index j even if the Qbar sets overlap. The main proof chain—from bramble duality (Theorem 5.2) to Theorem 6.1 to the cleaning lemma (Lemma 4.3)—is coherent, and the independence-number bounds used in the induction (α(N[S]) ≤ (d−1)|S|) are correct for K_{1,d}-free graphs. The only unsupported statement is the Section 1.1 algorithmic claim: 'our proofs are constructive... imply an algorithm... in time |V(G)|^{g(k,d)}'—no algorithm or complexity analysis is given anywhere in the paper. This does not affect the central theorem but is presented as a contribution and should be either proved or removed.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every positive integer k and d≥2, every K_{1,d}-free graph either contains the k-skinny ladder as an induced minor or has tree-independence number bounded by an explicit function τ(k,d). Since the k-skinny ladder contains the k-ladder as an induced minor, this establishes the headline ladder theorem. The proof combines a strong-bramble duality theorem (Theorem 2.3), a lemma producing two non-adjacent induced paths whose closed neighborhoods cannot be separated by a set of small independence number (Theorem 5.2), and a Menger-like construction (Theorem 6.1) that builds a large shuffled rope ladder, which is then cleaned into a rope ladder (Lemma 4.3) and converted into a skinny ladder. The paper also derives applications: an improved bound for wheel exclusion, a bounded tree-independence number for graphs excluding long thetas and long prisms, and an induced Erdos-Posa-type statement for connected induced subgraphs of skinny ladders in K_{1,d}-free graphs.","tokens_in":27008,"tokens_out":4690,"duration_ms":45366,"significance":"If correct, the main theorem is a substantial advance toward the induced grid conjecture for K_{1,d}-free graphs: it gives the first family of planar obstructions handled beyond wheels/tripods, with explicit elementary bounds and a relatively uniform proof strategy. The paper is honest about using strong bramble duality and the prior result Lemma 2.4 from [CHMW25] as black boxes, and these uses are legitimate. The applications to wheels, long thetas/prisms, and induced Erdos-Posa are nontrivial and improve known bounds. The main proof chain from Theorem 5.2, Theorem 6.1, and Lemma 4.3 to Theorem 1.4 is internally consistent, and I found no circularity. The manuscript would be a valuable contribution after addressing the unproved algorithmic claim and a few local issues in the applications.","major_comments":[{"comment":"The paper states: 'our proofs are constructive, and with the result of [CHMW25], they imply an algorithm ... in time |V(G)|^{g(k,d)}'. No algorithm or complexity analysis is provided anywhere in the manuscript. Since this is advertised as a contribution, please either give a precise constructive argument (including the choice of g) or remove/qualify the claim. This does not affect the correctness of Theorem 1.4, but as written it is an unsupported statement.","section":"§1.1"},{"comment":"The statement assumes ℓ ≥ 12(d−1)^2(2k−1)+1, but the greedy argument in the proof discards up to 4(d−1)^2(2k−1) indices after each chosen index and needs four chosen indices. The proof itself later uses ℓ ≥ 16(d−1)^2(2k−1). With the stated 12(d−1)^2(2k−1)+1 the greedy selection may fail. This is a local numerical error, but it affects Theorem 1.6 and should be corrected in the statement and in Corollary 7.7.","section":"Lemma 7.10"}],"minor_comments":[{"comment":"The final step of Theorem 6.1 asserts that each R_i has length at least 4 'since w_i is adjacent to a vertex in R_i that is not an endpoint or second-endpoint'. This is correct, but the one-sentence justification relies on the earlier deletion of S^i and on the definition of Qbar^i_{t_i}; please expand it for readability.","section":"§6.1"},{"comment":"In the induction step, 'ℓi' should be 'ℓ^i' (powers of ℓ), matching the later bounds involving ℓ^j. The current notation could confuse.","section":"§6.1"},{"comment":"In the proof of Theorem 7.3, 'β(s´2)' appears to be a typo for 'β(s_2)'. Please correct.","section":"§7.1"},{"comment":"There are several typos: 'grpah' (p.1), 'combarability' (p.1), 'T heorem1.4' (p.3), 'InrCHT24s' (p.21), 'doe snot' (p.19), 'we loose control' (p.25). A careful proofreading pass is needed.","section":"Throughout"},{"comment":"Theorem 5.2 is stated as a direct consequence of the proof of Theorem 5.1, but it is not formally proved. Since it is load-bearing for Theorem 1.4, please include a short proof or explicitly say it follows by the same argument with P2 = R.","section":"Theorem 5.2"}],"recommendation":"minor_revision","confidential_remarks":"The main theorem appears correct and the proof strategy is coherent. The unproved algorithmic claim and the numerical error in Lemma 7.10 are local and fixable; neither undermines Theorem 1.4. I recommend minor revision rather than major revision because the central contribution is sound and the issues can be addressed without changing the proof architecture."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result is real. Excluding the k-ladder as an induced minor in K_{1,d}-free graphs gives bounded tree-independence number, and the skinny-ladder strengthening in Theorem 1.4 is a genuine improvement. The paper also delivers tangible corollaries: better bounds for wheels, a new result for long thetas and prisms, and an induced Erdős-Pósa extension. The proof architecture, using bramble duality and the authors' earlier CHMW25 lemma as black boxes, is coherent and not circular. I looked specifically at the flagged length-at-least-4 assertion in Theorem 6.1; it is sound. Since w_{i+1} lies in Qbar^i_{t_i} = N[R_i] \\setminus N[S^i], it has a neighbor on R_i that is not an endpoint or second-endpoint, which forces |R_i| \\ge 4. The pigeonhole step about multiple Qbar sets is also fine. So I would not hang a rejection on that point.\n\nThe soft spots are real but not load-bearing. The Section 1.1 claim that the proofs are constructive and imply an algorithm running in |V(G)|^{g(k,d)} is unsupported: no algorithm, no complexity analysis, no details anywhere. Since it is presented as a contribution, the authors should either prove it or delete it. There are also minor typos and some arguments delegated with phrases like \"analogously\" or \"as depicted\"; a referee will want those case analyses written out. None of that undermines the central theorem.\n\nI disagree slightly with the conditional verdict. The main mathematical argument holds up as far as I can see, and the unsupported algorithmic remark is a localized issue, not a reason to doubt the theorem. The paper is carefully connected to the existing literature, and the reliance on the authors' own prior bramble lemma is transparent and parameter-free. This is a solid contribution to the structural study of induced minors and tree-independence number.\n\nWho should read it: anyone working on induced grid-type theorems, tree-independence number, or K_{1,d}-free graph structure. It deserves a serious referee. My recommendation: send it to peer review, and ask the referee to make the authors prove or drop the algorithmic claim and to expand the delegated proof sketches.","headline":"Genuine new width-obstruction result for ladders in K_{1,d}-free graphs, with coherent proof and useful corollaries; the only real blemish is an unproved algorithmic claim in Section 1.1.","tokens_in":27475,"tokens_out":1557,"would_cite":true,"duration_ms":17667,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C75","05C83","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that in K_{1,d}-free graphs, excluding the k-ladder as an induced minor forces a tree-decomposition whose bags have bounded independence number.","keywords":["induced minors","ladder graphs","tree-independence number","K_{1,d}-free graphs","strong brambles","induced Erdos-Posa property","long thetas","long prisms"],"falsifier":"Build a K_{1,3}-free graph with two non-adjacent induced paths P and H such that every separator between N[P] and N[H] has independence number at least eta(2,3)=432, yet no 2-H-rope ladder appears as an induced subgraph.","tokens_in":1827,"feed_emoji":"🪜","tokens_out":4177,"duration_ms":127041,"temperature":0.7,"pith_summary":"The paper's goal is a structural dichotomy: any graph that avoids a large induced star and also avoids a k-ladder as an induced minor must have small tree-independence number. Equivalently, if tree-independence number is large, the graph must contain a k-skinny ladder (a ladder with each rung subdivided once) as an induced minor. The proof builds the ladder by finding two non-adjacent induced paths and many mutually non-adjacent connector paths, then sorting them into a rope ladder that contracts to the skinny ladder. This is the first step toward an induced grid theorem for K_{1,d}-free graphs, and it implies several known results about wheels, long thetas, long prisms, and induced cycles.","feed_headline":"Forbidding k-ladders and induced stars bounds tree-independence","feed_subtitle":"Absence of the k-ladder as induced minor forces bags of bounded independence, a step toward an induced grid theorem.","key_machinery":"Shuffled rope ladders: two non-adjacent induced paths P1,P2 plus k pairwise non-adjacent induced paths Phi_i, each with neighbours on both rails. A cleaning lemma sorts the attachment orders to make a rope ladder; contracting its rungs gives the k-skinny ladder. The engine is Theorem 6.1, a Menger-like statement that turns a separator-resistance condition between a fixed subgraph H and an induced path P into an ell-H-rope ladder. Its proof greedily selects shortest mutually non-adjacent paths while managing endpoints and second-endpoints, which keeps the final rail path induced.","core_discovery":"The central claim is Theorem 1.4: there is a function tau(k,d) such that every K_{1,d}-free graph with tree-independence number at least tau(k,d) contains the k-skinny ladder as an induced minor. Since the skinny ladder contains the k-ladder as an induced minor, the analogous statement for k-ladders follows. The proof proceeds from a large tree-independence number to a strong bramble, then to two non-adjacent induced paths whose closed neighbourhoods cannot be separated by a small-independence set, then to a large shuffled rope ladder, then to a rope ladder, and finally to the skinny ladder by contraction.","pith_inferences":["Theorem 6.1 fixes one side H and allows the path P to be replaced; a symmetric, two-side-fixed version would amount to an induced Menger theorem that remains open.","The bounds are recursive and likely far from optimal, so the theorem should be read as qualitative.","If one could force rung paths to be distance-2 separated, the double-ladder step toward the induced grid would become visible.","The cycle-rope-ladder structure could be the basis for a two-cycle version needed for double wheels."],"forward_implications":["In K_{1,d}-free graphs, forbidding the k-ladder as induced minor bounds the independence number of every bag in a tree-decomposition.","The skinny-ladder version yields an independence Erdos-Posa property for every connected induced subgraph of a k-skinny ladder.","The method gives a sharper bound for wheel exclusion and a generalisation of the theta/prism theorem to k-long thetas and prisms.","The proof is constructive, so for fixed k,d one can either find the ladder or construct the decomposition algorithmically.","The same construction underlies several previously separate results, suggesting the ladder is the common obstruction."],"supporting_citations":[{"why":"Provides the bramble duality underlying the tree-independence number.","marker":"[Adl06]"},{"why":"Supplies the strong-bramble lemmas and path-hitting lemma used in Section 5.","marker":"[CHMW25]"},{"why":"Used to sort shuffled rung paths into a rope ladder.","marker":"[ES35]"},{"why":"Gives the theta/prism exclusion result that Theorem 1.6 strengthens.","marker":"[CHT24]"},{"why":"Provides the coarse Erdos-Posa theorem whose K_{1,d}-free consequences are extended here.","marker":"[AGHjK25a]"},{"why":"Supplies the long-cycle Erdos-Posa theorem used as a baseline in Section 7.1.","marker":"[AGHjK25b]"},{"why":"Shows the bounded-degree grid theorem, the qualitative benchmark for the induced setting.","marker":"[Kor23]"}],"fun_headline_variants":["Star-free and ladder-free graphs get bounded tree-independence","Forbidding induced stars and ladders tames tree-independence","How to force a ladder: large tree-independence means skinny ladder","Without induced stars or ladders, tree-independence is bounded","Excluding induced stars and ladders bounds tree-independence"],"cache_read_input_tokens":29184,"weakest_assumption_plain":"The proof of Theorem 6.1 relies on each chosen connector path attaching to the previous path through a vertex that is not an endpoint or second-endpoint; if attachments could only happen at those boundary vertices, the assembled rail path would not be induced.","fun_headline_variants_meta":{"raw":{"variants":["Star-free and ladder-free graphs get bounded tree-independence","Forbidding induced stars and ladders tames tree-independence","How to force a ladder: large tree-independence means skinny ladder","Without induced stars or ladders, tree-independence is bounded","Excluding induced stars and ladders bounds tree-independence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000897,"raw_usage":{"total_tokens":3724,"prompt_tokens":792,"completion_tokens":2932,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":536,"completion_tokens_details":{"reasoning_tokens":2846}},"tokens_in":536,"tokens_out":2932,"duration_ms":22136,"temperature":1.0,"reasoning_tokens":2846,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T10:27:31.075723+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a K_{1,3}-free graph with two non-adjacent induced paths P and H such that every separator between N[P] and N[H] has independence number at least eta(2,3)=432, yet no 2-H-rope ladder appears as an induced subgraph.","supporting_citations":[],"review_version":1}