{"id":"dd9db163-2654-4c80-947c-ec1bd3ea6bf8","arxiv_id":"2411.19173","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every K_{s,s}-free graph with an n-vertex path contains an induced path of length Ω(log log n / log log log n), nearly matching the known upper bound.","lead":"This paper proves that every graph avoiding a complete bipartite pattern, if it contains a path on n vertices, must contain an induced path of length about log log n divided by log log log n. The result nearly closes a 40-year-old question and is proved in just a few pages.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: after checking the random-walk argument and the degenerate-case lemma, the proof of Theorem 1.1 is sound up to a one-line repair in Lemma 2.2.","rationale":"The paper proves Theorem 1.1 by splitting into a degenerate case and a high-minimum-degree case. The high-degree case uses a reversible random walk and an auxiliary directed graph H. The potentially problematic line is the estimate P[vivj in E(G) and E] <= 4s d^{-1/s}: the printed justification via conditional probability on E is not logically immediate, because E involves many other constraints on the walk. But the correct justification is short: E implies v_{j-1} not-> v_i, and conditional on that event, at most (4s/d^{1/s})|N(v_{j-1})| of the at least d neighbours of v_{j-1} are adjacent to v_i. Since P(A and E) <= P(A and B) <= P(A | B), the same constant 4s d^{-1/s} follows. This repair does not change any later bound, so the conclusion that the walk is an induced path with positive probability holds. Lemma 2.1, which the reader flagged, is also sound: with t = d^{1/s}/s, the key inequality |U| = st <= 2d/t follows from st^2 <= d^{2/s}/s <= 2d, so the edge-counting contradiction works. The use of real-valued t and a set of size st is a minor formal sloppiness, but in the application one may take a set of size ceil(st) without changing the argument. The degenerate case relies on Claim 2.4, whose BFS tree argument is valid: a directed edge skipping levels would contradict BFS distances, and a backward edge along a root-to-leaf path would create a directed cycle. The reversal construction in Lemma 2.3 preserves outdegree at most d+1 and acyclicity, yielding the stated log-log bound. Overall, I find no load-bearing gap; the concerns are typographical or expository and do not threaten the central claim.","tokens_in":4968,"tokens_out":25787,"duration_ms":222023,"concrete_test":"Verify Lemma 2.2 by replacing the displayed inequality with P(A and E) <= P(A and B) <= P(A | B), where A = {v_i v_j in E(G)} and B = {v_{j-1} not-> v_i}, and recompute the final probability bound; if the bound remains at most 1/(4s^2) d^{2/s-1} + 1/(2s) < 1 for s >= 2, the high-degree case of Theorem 1.1 is intact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing concern. The central claim rests on Lemma 2.2, and the only delicate step is the bound P[vivj in E(G) and E] <= 4s d^{-1/s}. As printed, the chain P[A and E] <= P[A | E] <= 4s d^{-1/s} is not justified, since conditioning on E may distort the distribution of vj. However, the intended estimate is valid: E implies B = {v_{j-1} not-> v_i}, so P(A and E) <= P(A and B) <= P(A | B), and conditional on B, at most (4s/d^{1/s})|N(v_{j-1})| of the uniformly chosen neighbours of v_{j-1} are adjacent to v_i, giving the same bound. Lemma 2.1's constants are also correct after substituting t = d^{1/s}/s; the reported misprint does not affect the inequality |U| <= (2/t)|N(v)|. Claim 2.4's BFS argument is standard and valid. Thus no assumption on which the theorem depends appears false or materially weak.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1.1: every K_{s,s}-free graph on n vertices that contains a path on n vertices contains an induced path of length at least Ω(log log n / log log log n). The proof is short and splits into two cases. If the graph is d-degenerate for d=(log log n)^{2s}, Lemma 2.3 (the Nešetřil-Ossona de Mendez bound, proved in full) gives an induced path of length Ω(log log n / log log log n). Otherwise, a subgraph of minimum degree at least d exists, and Lemma 2.2 gives an induced path of length Ω(log log n). Lemma 2.2 is proved by a random walk on the graph, using an auxiliary directed graph H of vertices with large common neighborhoods; Lemma 2.1 controls the outdegree of H via the Kővári-Sós-Turán theorem. Combined with the Couëtoux-Defrain-Raymond upper bound O(log log n · log log log n), this essentially resolves the 1982 problem of Galvin, Rival and Sands.","tokens_in":5196,"tokens_out":5324,"duration_ms":45886,"significance":"This is a significant result. It improves the previous lower bound (log log n)^{1/5-o(1)} to (log log n)^{1-o(1)}, which is within a factor O(log log log n) of the best known upper bound. The proof is remarkably short and self-contained: the only external inputs are the standard Kővári-Sós-Turán theorem and a degeneracy argument that the authors include in full. There are no fitted parameters and no circularity; the argument appears to be robust. The random-walk technique in Lemma 2.2 is elegant and may well be useful for other induced-subgraph problems in K_{s,s}-free graphs. If the paper is correct, it nearly closes a 40-year-old problem with a clean argument, and it will be of interest to the extremal graph theory community.","major_comments":[],"minor_comments":[{"comment":"In the proof of Lemma 2.1, the line '|U| = st ≤ 2/t d ≤ 2/t |N(v)|, which follows from the assumption st ≤ d^{1/s}/s' contains a misprint: the stated hypothesis is t ≤ d^{1/s}/s, which gives st ≤ d^{1/s}, not st ≤ d^{1/s}/s. The conclusion is nevertheless correct, since st ≤ d^{1/s} and d^{1/s} ≤ 2d/t for all s≥2 and d≥2, so this is only a typo and does not affect the argument.","section":"Lemma 2.1"},{"comment":"The displayed chain 'P[v_i v_j ∈ E(G) and E] ≤ P[v_i v_j ∈ E(G) | E] ≤ 4s d^{-1/s}' is not justified as written: conditioning on E can bias the distribution of v_j, so the observation for the event v_{j-1} not→ v_i does not immediately transfer to conditioning on E. The intended estimate is valid, however, by the following repair: if B denotes the event v_{j-1} not→ v_i, then E implies B, so P(A ∩ E) ≤ P(A ∩ B) ≤ P(A | B) ≤ 4s d^{-1/s}. The authors should replace the displayed chain with this argument.","section":"Lemma 2.2"},{"comment":"There is a complement typo around the definition of the event E. The text defines E as 'the probability that there is no edge v_j → v_i' but then writes P(E) = P[v_j → vi for some ...] and later uses 'E does not happen' to denote the presence of such an edge. The displayed union bound should refer to P(not E), not P(E); the subsequent calculation remains correct once this notation is fixed.","section":"Lemma 2.2"},{"comment":"The abstract and introduction say 'a K_{s,s}-free graphs' where the plural is a grammatical slip; this should read 'a K_{s,s}-free graph'. This is a typographical issue only.","section":"Introduction"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something genuinely new: it improves the lower bound for induced paths in K_{s,s}-free graphs from (log log n)^{1/5-o(1)} to (log log n)^{1-o(1)}, matching the existing upper bound up to a factor of log log log n. That essentially settles the Galvin–Rival–Sands problem. The proof is short, self-contained, and largely clean; the random-walk lemma (Lemma 2.2) is the core idea and it works.\n\nWhat I like: the argument is honest and doesn't hide anything. The degeneracy case is handled by the Nešetřil–Ossona de Mendez lemma, and the authors include a full proof of that lemma for completeness. The high-minimum-degree case uses a clever but simple random walk. The KST bound is applied correctly. There are no fitted parameters, and the result does not assume what it proves.\n\nThe soft spots are minor and typos, not mathematical. In Lemma 2.1 the justification for |U| ≤ 2d/t cites a condition 'st ≤ d^{1/s}/s' when the stated hypothesis is 't ≤ d^{1/s}/s'; after substituting t = d^{1/s}/s the inequality holds, so this is a misprint. In Lemma 2.2, the printed step P[v_i v_j ∈ E(G) and E] ≤ P[v_i v_j ∈ E(G)|E] ≤ 4s d^{-1/s} is not justified as written, because conditioning on E changes the distribution of v_j. But the intended bound is valid: one can condition on the weaker event v_{j-1} not→ v_i, under which the distribution of v_j is still uniform over N(v_{j-1}), and the same 4s d^{-1/s} bound follows. So the proof survives a one-line repair. The stress-test note confirms this.\n\nI also checked the citation pattern. The only self-citation [9] is in the introduction and does no work. The upper bound from Couëtoux–Defrain–Raymond (arXiv:2507.22509) is cited properly, and the paper makes no claim that isn't supported.\n\nWho should read this: anyone working on induced subgraphs, degeneracy, or Ramsey-type questions in sparse graphs. It's a short note that resolves a known open problem up to iterated logarithms, and the proof technique (random walks on K_{s,s}-free graphs) is likely reusable.\n\nMy take: this deserves a serious referee. The typos should be fixed, but the mathematics is sound and the result is significant. Send it to peer review; I expect it to be accepted after minor revisions.","headline":"Short, self-contained proof improving the lower bound for induced paths in K_{s,s}-free graphs to (log log n)^{1-o(1)}, essentially closing a 40-year-old problem.","tokens_in":5782,"tokens_out":1486,"would_cite":true,"duration_ms":14216,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38","05C55","05C81"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every $K_{s,s}$-free graph containing an $n$-vertex path contains an induced path of length at least $\\Omega(\\log\\log n/\\log\\log\\log n)$, nearly matching the known upper bound.","keywords":["induced paths","Ks,s-free graphs","Ramsey-type problem for paths","degenerate graphs","random walks","extremal graph theory","log log bounds"],"falsifier":"Check the algebra in Lemma 2.1 by substituting the stated hypothesis $t\\le d^{1/s}/s$ into $|U|=st$ and verifying the printed inequality $st\\le(2/t)d$; if the substitution fails, the contradiction in equation (1) collapses. A direct falsification would be a $K_{s,s}$-free graph of minimum degree $d$ in which some vertex $v$ has more than $d^{1/s}$ vertices $u$ with $|N(u)\\cap N(v)|\\ge(4s/d^{1/s})|N(v)|$, since Lemma 2.1 forbids exactly that.","tokens_in":4780,"feed_emoji":"🛤️","tokens_out":13368,"duration_ms":103423,"temperature":0.7,"pith_summary":"This note closes a gap that has stood since 1982 by proving that every $K_{s,s}$-free graph containing a path on $n$ vertices must contain an induced path of length at least $\\Omega(\\log\\log n/\\log\\log\\log n)$. The previous best lower bound was only $(\\log\\log n)^{1/5-o(1)}$, and a known construction shows that no proof can push the answer beyond $O(\\log\\log n\\cdot\\log\\log\\log n)$, so the two bounds now meet up to an iterated-logarithmic factor. The argument is short and self-contained: if the graph is $d$-degenerate, a breadth-first-search lemma already gives the target length; otherwise a subgraph of minimum degree at least $d$ contains a long induced path produced by a random walk. Choosing $d=(\\log\\log n)^{2s}$ balances the two cases and yields the theorem.","feed_headline":"Proof closes 1982 gap on induced paths in Ks,s-free graphs","feed_subtitle":"Every Ks,s-free graph with an n-vertex path has an induced path of length at least (log log n)/(log log log n).","key_machinery":"The load-bearing construction is a random walk of length $k=\\lceil d^{1/(2s)}/(2s)\\rceil$ on a subgraph of minimum degree $d$, together with an auxiliary directed graph $H$ in which $v\\to u$ means $u$ shares at least $(4s/d^{1/s})|N(v)|$ neighbours with $v$. A counting lemma, proved via the standard extremal bound for bipartite graphs with no $K_{s,s}$ (the complete bipartite graph with $s$ vertices on each side), shows that every vertex has outdegree at most $d^{1/s}$ in $H$. The random walk then has two good properties with positive probability: no later vertex points to an earlier vertex, and no chord appears between non-consecutive vertices. A union bound over the $O(k^2)$ bad pairs keeps the failure probability strictly below $1$, so the walk itself is an induced path of length about $d^{1/(2s)}/(2s)$.","core_discovery":"The paper's central claim is that the guaranteed length of an induced path in a $K_{s,s}$-free graph with an $n$-vertex path jumps from $(\\log\\log n)^{1/5-o(1)}$ to $(\\log\\log n)^{1-o(1)}$. The proof shows that the non-degenerate case is comparatively easy: any $K_{s,s}$-free subgraph of minimum degree $d$ contains an induced path of length at least $d^{1/(2s)}/(2s)$, obtained by sampling a random walk and proving with positive probability that it has no chords and no forbidden reverse edges. The degenerate case is handled by a lemma that every $d$-degenerate graph with a Hamilton path on $n$ vertices contains an induced path of length $\\Omega(\\log\\log n/\\log d)$. Setting $d=(\\log\\log n)^{2s}$ and combining the two cases gives Theorem 1.1.","pith_inferences":["A natural next step, not taken in the paper, is to check whether the random-walk lemma extends to any hereditary class where the \"large common neighbourhood\" set of a vertex can be bounded; the proof only needs that bound and the degeneracy argument.","If Lemma 2.1's constant can be sharpened, the final denominator $\\log\\log\\log n$ may be removable: the non-degenerate case already gives $\\Omega(d^{1/(2s)})$, which is stronger than the theorem needs.","Because the known extremal examples are 2-degenerate and $K_{3,3}$-free, the remaining gap may be a degeneracy phenomenon rather than an $s$-dependent one; testing small $s$ could confirm this."],"forward_implications":["The guaranteed induced-path length in $K_{s,s}$-free graphs is now pinned between $\\Omega(\\log\\log n/\\log\\log\\log n)$ and $O(\\log\\log n\\cdot\\log\\log\\log n)$, essentially settling the 1982 problem.","In the non-degenerate regime the bound is stronger: any $K_{s,s}$-free graph with minimum degree $d$ contains an induced path of length $\\Omega(d^{1/(2s)})$, which at the proof's threshold $d=(\\log\\log n)^{2s}$ is already $\\Omega(\\log\\log n)$.","The gap between the new lower bound and the known upper bound is only a factor of $O((\\log\\log\\log n)^2)$, so any future improvement must attack the iterated-logarithmic denominator rather than the $\\log\\log n$ scale.","The two-case split means the theorem holds for every fixed $s\\ge 2$, with the $\\Omega(\\cdot)$ constant depending on $s$; the high-minimum-degree subcase is what supersedes the previous lower bound for all such $s$."],"supporting_citations":[{"why":"posed the original problem and supplied the first lower bound, whose scale this paper improves","marker":"[8]"},{"why":"gave the previous best lower bound $(\\log\\log n)^{1/5-o(1)}$ that Theorem 1.1 supersedes","marker":"[4]"},{"why":"constructed 2-degenerate examples with no induced path longer than $O(\\log\\log n\\cdot\\log\\log\\log n)$, making Theorem 1.1 nearly tight","marker":"[3]"},{"why":"provided the degeneracy lemma, reproduced in the paper, that handles the $d$-degenerate case","marker":"[10]"},{"why":"supplies the standard extremal bound for bipartite graphs with no $K_{s,s}$ used in Lemma 2.1","marker":"[2]"},{"why":"gave the earlier upper-bound construction that the sharper example of [3] builds on","marker":"[5]"}],"fun_headline_variants":["Induced path gap essentially closed for Ks,s-free graphs","Short proof nails induced path bound in Ks,s-free graphs","Essentially solves 1982 induced path problem for Ks,s-free graphs","Nearly optimal induced path length in Ks,s-free graphs","Sharp bound for induced paths in Ks,s-free graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on Lemma 2.1's bound that, in a $K_{s,s}$-free graph of minimum degree $d$, a fixed vertex has at most about $d^{1/s}$ vertices sharing a large common neighbourhood with it; the printed derivation of the key inequality $|U|=st\\le(2/t)d$ appears to contain a misprinted exponent ($st\\le d^{1/s}/s$ in place of the hypothesis $t\\le d^{1/s}/s$), and if that bound failed with a materially worse constant the random-walk failure probability would not stay below $1$.","fun_headline_variants_meta":{"raw":{"variants":["Induced path gap essentially closed for Ks,s-free graphs","Short proof nails induced path bound in Ks,s-free graphs","Essentially solves 1982 induced path problem for Ks,s-free graphs","Nearly optimal induced path length in Ks,s-free graphs","Sharp bound for induced paths in Ks,s-free graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001012,"raw_usage":{"total_tokens":4259,"prompt_tokens":916,"completion_tokens":3343,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":3266}},"tokens_in":532,"tokens_out":3343,"duration_ms":21612,"temperature":1.0,"reasoning_tokens":3266,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T10:28:19.348629+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the algebra in Lemma 2.1 by substituting the stated hypothesis $t\\le d^{1/s}/s$ into $|U|=st$ and verifying the printed inequality $st\\le(2/t)d$; if the substitution fails, the contradiction in equation (1) collapses. A direct falsification would be a $K_{s,s}$-free graph of minimum degree $d$ in which some vertex $v$ has more than $d^{1/s}$ vertices $u$ with $|N(u)\\cap N(v)|\\ge(4s/d^{1/s})|N(v)|$, since Lemma 2.1 forbids exactly that.","supporting_citations":[{"cited_title":"Galvin, I","cited_arxiv_id":null,"evidence_quote":"posed the original problem and supplied the first lower bound, whose scale this paper improves"},{"cited_title":"Couëtoux, O","cited_arxiv_id":null,"evidence_quote":"constructed 2-degenerate examples with no induced path longer than $O(\\log\\log n\\cdot\\log\\log\\log n)$, making Theorem 1.1 nearly tight"},{"cited_title":"Nešetřil and P","cited_arxiv_id":null,"evidence_quote":"provided the degeneracy lemma, reproduced in the paper, that handles the $d$-degenerate case"},{"cited_title":"Bollobás,Extremal Graph Theory, Dover Publications, 2004","cited_arxiv_id":null,"evidence_quote":"supplies the standard extremal bound for bipartite graphs with no $K_{s,s}$ used in Lemma 2.1"},{"cited_title":"Defrain and J.-F","cited_arxiv_id":null,"evidence_quote":"gave the earlier upper-bound construction that the sharper example of [3] builds on"}],"review_version":1}