{"id":"5c63b2c3-4f6d-4928-a1da-be70dd88fac9","arxiv_id":"2607.13995","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For {P_s,K_{t,t}}-free graphs, the maximum path length is at most 2^{ω(G)^c}, and treedepth is clique-polynomial.","lead":"This paper improves the best known upper bound on how long a path a graph can contain when it forbids both long induced paths and large induced bicliques, reducing it from a doubly exponential to a singly exponential function of its clique number. It also proves that in every hereditary graph class, if treedepth is bounded by any function of clique number, then it is bounded by a polynomial.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main results depend on Theorem 6 (Hajebi 2025) — pathwidth clique-polynomiality — via Corollary 7; if this unrefereed result fails, the single-exponential and polynomial bounds collapse.","rationale":"The reader's weakest_assumption exactly identifies the dependence on Theorem 6 (and, more broadly, Theorem 5). My review confirms that Theorem 5 is not fragile: it follows from the classical Galvin–Rival–Sands bound on path number for bounded ω and the standard inequality pw(G) ≤ pn(G)−1, so the only real exposure is Theorem 6. The internal lemmas (Theorems 11 and 12) appear correct, and the algebra in Theorems 2–4 checks out modulo the plain-text rendering of superscripts. The concern is thus not an internal inconsistency but an external, unverified dependency. Because the paper itself is transparent about this dependency and the reader already assigned moderate confidence, I do not think the verdict should change; acceptance is appropriate if one trusts Hajebi's preprint. A concrete verification (or refutation) of Theorem 6 would settle the matter. Therefore I recommend UNCHANGED, in agreement with the reader's assessment.","tokens_in":10441,"tokens_out":26901,"duration_ms":241010,"concrete_test":"Verify Theorem 6 by attempting to construct a hereditary class C containing, for each k, a graph G_k with ω(G_k)=k and pw(G_k)=2^k while every induced subgraph H satisfies pw(H) ≤ 2^{ω(H)}. If such a class exists, Theorem 6 is false and Corollary 7 collapses. A promising starting point is to adapt the Chudnovsky–Trotignon [10] construction that shows treewidth is not clique-polynomial. If the adaptation provably fails (e.g., because pathwidth satisfies a polynomial-type recurrence that treewidth does not), then the concern is resolved. Alternatively, a close reading of the proof of Theorem 6 in arXiv:2510.19120 should identify whether it uses any hidden assumption beyond hereditariness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative theorems (Theorem 2, 3, and the derived Theorem 4) all pass through Corollary 7, which asserts pw(G) ≤ ω(G)^c for {P_s,K_{t,t}}-free graphs. Corollary 7 is obtained by combining Theorem 5 (which, as the authors note, follows from Galvin–Rival–Sands and pw ≤ pn−1, so is on solid classical ground) with Theorem 6, the recent preprint claim that pathwidth is clique-polynomial. The proof of Theorem 6 is not reproduced, and no alternative derivation of Corollary 7 is furnished. If Theorem 6 is false — e.g., if some hereditary class has pathwidth bounded by a super-polynomial function of clique number — then the step from 'pathwidth is bounded by some function of ω' to 'pathwidth is bounded by a polynomial in ω' fails. The best available replacement would be the doubly exponential bound on pn from Hunter et al., which would turn the pn bound in Theorem 2 into a doubly exponential (or worse) function, and the td bound in Theorem 3 into a non-polynomial function. Thus all main claims are conditional on the correctness of a single unrefereed external theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graphs with no induced path P_s and no induced biclique K_{t,t}. Its main quantitative claim (Theorem 2) is that the path number satisfies pn(G) ≤ 2^{ω(G)^c}, improving the previously known doubly exponential bound obtained from Hunter et al.; a tightness example based on transitive closures of binary trees shows the exponential form is unavoidable up to the constant c. The paper further proves Theorem 3: for such graphs treedepth is bounded by a polynomial in ω(G), and derives Theorem 4, the treedepth analogue of Hajebi's clique-polynomiality of pathwidth. The proof route is: Theorem 5 gives pathwidth bounded by some function of ω; Hajebi's Theorem 6 converts this to a polynomial bound in Corollary 7; Theorem 12 converts pathwidth to path number and Theorem 11 converts pathwidth to treedepth in P_s-free graphs; Theorem 4 follows by choosing s and t to be 2^{f(2)}. The internal induction arguments appear coherent, and the main caveat is the reliance on the unrefereed Theorem 6.","tokens_in":10727,"tokens_out":20854,"duration_ms":201911,"significance":"Assuming the cited Hajebi theorem, the improvement from doubly exponential to singly exponential path number is a genuine quantitative advance, and the treedepth-polynomiality consequence is clean and likely to be useful. The paper is largely self-contained after Corollary 7; the induction proofs of Theorems 11 and 12 are transparent, and the binary-tree tightness example is simple and convincing. The main weakness is that the entire quantitative content is conditional on Theorem 6, a 2025 preprint whose proof is not reproduced. I do not see an internal circularity or a flaw in the reduction, but the dependence should be made explicit to the reader.","major_comments":[{"comment":"All of Theorems 2–4 pass through Corollary 7, whose proof invokes Theorem 6 from the unpublished preprint [17]. The manuscript does not reproduce or independently verify Theorem 6, and this is the only route from bounded pathwidth to polynomial pathwidth. If Theorem 6 were false, Theorem 2 would reduce to the doubly exponential bound and Theorem 3 would give only a nonpolynomial treedepth bound. I do not regard this as an internal error because the attribution is clear, but the paper should state in the introduction and abstract that the main results are conditional on Hajebi's theorem, or include a proof of Theorem 6 / Corollary 7 in an appendix.","section":"§2.1, Corollary 7"}],"minor_comments":[{"comment":"The phrase 'we improve the best known bound' may be read as an unconditional claim. Since the proof relies essentially on Theorem 6 from [17], a sentence such as 'modulo Hajebi's recent theorem' would be helpful.","section":"§1, Abstract"},{"comment":"The note that Theorem 5 'also follows immediately from [1,15] and [29]' would be easier to verify with one explanatory sentence, namely that Theorem 1 bounds pn(ω) and Fact 6 gives pw ≤ pn−1.","section":"§2.1, Theorem 5"},{"comment":"In the proof, the choice s = t = 2^{f(2)} should be displayed with braces; in the inline text it can be misread as 2·f(2).","section":"§6, Theorem 4"},{"comment":"The normalization of the polynomial p to one with equal positive coefficients is slightly awkward. A shorter argument using p(x) ≤ a(d+1)x^d ≤ x^{d+1} for x ≥ 2 would be clearer.","section":"§2.1, Corollary 7"},{"comment":"Reference [14] spells the name as 'Erdös'; the standard spelling is 'Erdős'.","section":"References"}],"recommendation":"minor_revision","confidential_remarks":"The only substantive concern is the dependence on Hajebi's preprint. If the journal's policy permits citing recent unrefereed preprints, I am comfortable with acceptance after the requested caveat is added. The internal mathematics is sound and the paper is a nice contribution. If the editors prefer self-containedness, the authors should be asked to supply a proof of Theorem 6, though that may be beyond the scope of the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the take: the paper proves a singly exponential bound on the path number of {P_s,K_{t,t}}-free graphs in terms of clique number, improving the previous doubly exponential bound, and gives a matching lower bound. That is a real advance on a 40-year-old theorem. The treedepth results are also new: a polynomial bound on treedepth for these classes, and a proof that treedepth is clique-polynomial for every hereditary class, paralleling Hajebi's pathwidth theorem. The proof of the clique-polynomiality statement is a neat compactness trick—choose s,t = 2^{f(2)} so that any forbidden path or biclique would force a contradiction via the path number—and the induction arguments in Theorems 11 and 12 are clean and easy to follow. The lower-bound family T_k^+ (transitive closures of binary trees) is simple and works.\n\nThe soft spot is the pilgrimage through Corollary 7: the polynomial pathwidth bound pw(G) ≤ ω(G)^c is the engine for Theorems 2 and 3, and it relies on Theorem 6, Hajebi's clique-polynomiality of pathwidth, which is a recent unrefereed preprint. If that fails, the results fall back to the doubly exponential bound. This is a genuine dependency, but it is explicitly flagged, and Theorem 5 itself is backed by older literature. So I read it as conditional, not flawed.\n\nThe paper is well-written, honest about its dependencies, and the mathematics inside is sound. It deserves a serious referee. For a reading group, it's a good example of how to build new results on a recent theorem, and the dependency discussion is instructive. I'd cite it if I worked on boundedness of graph parameters.","headline":"Singly exponential bound for path number in {P_s,K_{t,t}}-free graphs, with a matching lower bound, but the main theorems pass through Hajebi's unrefereed clique-polynomiality of pathwidth.","tokens_in":11267,"tokens_out":5407,"would_cite":true,"duration_ms":48429,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C75","05C69","05C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes a singly exponential bound on the path number of {P_s, K_{t,t}}-free graphs in terms of clique number, and shows treedepth of such graphs is polynomial in clique number.","keywords":["induced path","induced biclique","longest path","clique number","treedepth","hereditary graph class","clique-polynomiality","pathwidth"],"falsifier":"Exhibit a hereditary graph class in which treedepth is bounded by a function of clique number but is not polynomially bounded; this refutes Theorem 4. More directly, construct {P_s, K_{t,t}}-free graphs whose path number grows faster than 2^{ω^c} for every fixed c, contradicting Theorem 2. Also, check whether the recent unrefereed result asserting that pathwidth is clique-polynomial holds as stated; a counterexample would break Corollary 7 and the polynomial bounds of Theorems 2 and 3.","tokens_in":10316,"feed_emoji":"📈","tokens_out":7202,"duration_ms":56083,"temperature":0.7,"pith_summary":"The paper proves that in graphs excluding a path on s vertices and a balanced biclique K_{t,t} as induced subgraphs, the maximum number of vertices in a (not necessarily induced) path is at most 2^{ω(G)^c} for a constant c depending only on s and t. This replaces the previously known doubly exponential bound with a singly exponential one and is best possible apart from the value of c. The proof passes through pathwidth: the same graph classes are shown to have pathwidth polynomial in clique number, and two new linear relationships are derived, bounding treedepth and path number by (s−1)·pw(G) and s·pw(G), respectively. Consequently, treedepth of such graphs is polynomial in clique number, and this yields the result that treedepth is clique-polynomial: any hereditary graph class where treedepth is bounded by a function of clique number in fact has a polynomial bound.","feed_headline":"The longest path grows at most singly exponentially with clique number","feed_subtitle":"Improves the previous doubly exponential bound and yields polynomial treedepth for all such graph classes","key_machinery":"The argument rests on three elements. First, Corollary 7, imported from a structural decomposition result and a recent theorem on pathwidth, gives that {P_s, K_{t,t}}-free graphs have pathwidth polynomial in clique number. Second, two new linear inequalities for P_s-free graphs relate the network parameters to pathwidth: Theorem 11 gives td(G) ≤ (s−1)·pw(G), and Theorem 12 gives pn(G) ≤ s·pw(G)−1, proved by induction on the order and by removing a shortest path P that hits every bag of a path decomposition, which reduces pathwidth by at least 1. Third, the transitive closures of complete binary trees provide the matching exponential lower bound for Theorem 2.","core_discovery":"The central claim, Theorem 2, is that for all positive integers s and t there is a constant c such that every {P_s, K_{t,t}}-free graph G satisfies pn(G) ≤ 2^{ω(G)^c}. The authors show this is tight up to the choice of c by exhibiting transitive closures of complete binary trees T_k^+, which are {P_4, K_{2,2}}-free, have clique number k and path number 2^{k+1}−1, so exponential dependence on ω is unavoidable. The proof also establishes Theorem 3, that td(G) ≤ ω(G)^c for these classes, and Theorem 4, that treedepth is clique-polynomial for all hereditary graph classes.","pith_inferences":["A natural next step is to pin down the optimal value of c in Theorem 2; the construction only shows c must grow with s and t, not its exact rate.","The clique-polynomiality of treedepth suggests that algorithms whose running time depends polynomially on treedepth may run in polynomial time on any hereditary class with treedepth bounded by a function of clique number.","The same two-step route—structural polynomial pathwidth plus linear relationships—might generalize to other hereditary classes that exclude a finite set of graphs, or to parameters such as treewidth under additional assumptions.","Since Theorem 4's proof chooses s=t=2f(2), it does not give an explicit polynomial; extracting explicit exponents for natural classes would be a concrete follow-up."],"forward_implications":["The path number bound in Theorem 2 is the first singly exponential bound for {P_s, K_{t,t}}-free graphs, improving the doubly exponential bound that followed from a recent result on long induced paths in K_{s,s}-free graphs.","Theorem 3 yields a polynomial treedepth bound for these classes, making treedepth a polynomial function of clique number.","Theorem 4 establishes that treedepth is clique-polynomial for every hereditary graph class, mirroring the analogous result for pathwidth.","Theorem 12's improved relationship between path number and pathwidth yields a better bound on induced path length in graphs of bounded pathwidth: an induced path of order at least (n+1)^{1/(k−1)}−1.","The tightness examples show that the exponential form in Theorem 2 cannot be replaced by a subexponential bound, up to the value of c."],"fun_headline_variants":["Singly exponential path bound for induced path-free graphs","Best possible exponential path bound in clique number","Treedepth polynomial for clique-bounded hereditary families","Path length: exponential in clique number, now tight","Improved path bound and polynomial treedepth in one result"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The chain of proofs depends on Corollary 7, which asserts that {P_s, K_{t,t}}-free graphs have pathwidth polynomial in clique number; this corollary relies in turn on two imported results from the literature, one of them a recent unrefereed preprint, and if either of those fails the polynomial pathwidth bound—and with it the polynomial form of Theorems 2 and 3—collapses.","fun_headline_variants_meta":{"raw":{"variants":["Singly exponential path bound for induced path-free graphs","Best possible exponential path bound in clique number","Treedepth polynomial for clique-bounded hereditary families","Path length: exponential in clique number, now tight","Improved path bound and polynomial treedepth in one result"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1286,"prompt_tokens":724,"completion_tokens":562,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":487}},"tokens_in":468,"tokens_out":562,"duration_ms":6171,"temperature":1.0,"reasoning_tokens":487,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T03:04:49.256805+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a hereditary graph class in which treedepth is bounded by a function of clique number but is not polynomially bounded; this refutes Theorem 4. More directly, construct {P_s, K_{t,t}}-free graphs whose path number grows faster than 2^{ω^c} for every fixed c, contradicting Theorem 2. Also, check whether the recent unrefereed result asserting that pathwidth is clique-polynomial holds as stated; a counterexample would break Corollary 7 and the polynomial bounds of Theorems 2 and 3.","supporting_citations":[],"review_version":1}