REVIEW 4 minor 1 cited by
Long induced paths in $K_{s, s}$-free graphs
T0 review · 0 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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)$.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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$.
Editorial extensions
If this is right
- 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$.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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.
minor comments (4)
- [Lemma 2.1] 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.
- [Lemma 2.2] 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.
- [Lemma 2.2] 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.
- [Introduction] 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.
Circularity Check
The derivation is self-contained; the only self-citation is contextual and not load-bearing.
full rationale
The proof of Theorem 1.1 splits into a degeneracy case and a high-minimum-degree case. The high-degree case is Lemma 2.2, whose proof uses only the random-walk stationarity/reversibility fact and Lemma 2.1; Lemma 2.1 is an elementary double-counting argument applying the classical Kovari-Sos-Turan bound, an external, parameter-free theorem. No fitted parameter is used: the threshold d=(log log n)^{2s} is chosen as a function of n and s only, and the factor 4s/d^{1/s} in the auxiliary digraph is fixed by the hypotheses of Lemma 2.1, not calibrated to make the final bound true. The only self-citation is [9] in the introduction's survey of Turan-type questions; it is not invoked in the proof, and no uniqueness or existence assertion is imported from it. Lemma 2.3 is a reproduction of Nesetril and Ossona de Mendez's result; although its proof is given 'for completeness', it does not depend on the paper's own claims. One minor conditioning line in Lemma 2.2 (P[... and E] <= P[...|E] <= 4sd^{-1/s}) is not justified as printed because the conditional probability bound was proved only under the weaker event v_{j-1} not-> v_i; but the intended bound holds by intersecting with the larger event, so this is a correctness typo, not circularity. Consequently no claim reduces by definition or self-citation to its own input.
Assumptions & free parameters
assumptions (4)
- standard math Kővári-Sós-Turán theorem for K_{s,s}-free bipartite graphs
- standard math Every d-degenerate graph has an acyclic orientation with maximum outdegree at most d
- standard math Reversibility of the simple random walk with stationary initial distribution on an undirected graph
- standard math Breadth-first search in an acyclic digraph yields induced root-to-leaf paths
Cite this review
Pith. "Pith review of Long induced paths in $K_{s, s}$-free graphs." pith.science (2026). https://pith.science/paper/VRGMVVDM
@misc{pith2026241119173,
author = {Pith},
title = {Pith review of: Long induced paths in $K_s, s$-free graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/VRGMVVDM}},
note = {Machine review of arXiv:2411.19173}
}
abstract
More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$-free graph containing an $n$-vertex path must contain an induced path of length $f(n)$, where $f(n)\to \infty$ as $n\to \infty$. Recently, it was shown by Duron, Esperet and Raymond that one can take $f(n)=(\log \log n)^{1/5-o(1)}$. In this note, we give a short self-contained proof that a $K_{s, s}$-free graphs with an $n$-vertex path contains an induced path of length at least $(\log \log n)^{1-o(1)}$. Combined with the recent remarkable example of Cou\"etoux, Defrain, and Raymond, which provides an upper bound of $O((\log \log n)^{1+o(1)})$, this essentially resolves this old problem.
Forward citations
Cited by 1 Pith paper
-
Graph classes through the lens of logic
A survey presenting first-order transductions as a unifying lens for graph classes, connecting sparsity, twin-width, and monadic stability and dependence.
Reference graph
Works this paper leans on
-
[9]
K\H{o}v\'ari-S\'os-Tur\'an theorem for hereditary families
Z. Hunter, A. Milojević, B. Sudakov and I. Tomon,Kővári-Sós-Turán theorem for hereditary families, preprint, arXiv:2401.10853
-
[1]
A. Atminas, V. V. Lozin, and I. Razgon,Linear time algorithm for computing a small biclique in graphs without long induced paths, inAlgorithm theory—SWAT 2012, 142–152, Lecture Notes in Comput. Sci., 7357, Springer, Heidelberg
work page 2012
-
[2]
Bollobás,Extremal Graph Theory, Dover Publications, 2004
B. Bollobás,Extremal Graph Theory, Dover Publications, 2004
work page 2004
-
[3]
B. Couëtoux, O. Defrain, and J.-F. Raymond,A quasi-optimal upper bound for induced paths in sparse graphs, preprint, arXiv:2507.22509
- [4]
-
[5]
O. Defrain and J.-F. Raymond,Sparse graphs without long induced paths, J. Combin. Theory Ser. B 166 (2024), 30–49
work page 2024
- [6]
- [7]
Show all 11 references
-
[8]
Galvin, I
F. Galvin, I. Rival, and B. Sands,A Ramsey-type theorem for traceable graphs, J. Combin. Theory Ser. B 33 (1982), 7–16
1982
-
[10]
Nešetřil and P
J. Nešetřil and P. Ossona de Mendez,Sparsity, Springer, 2012
2012
-
[11]
Smorodinsky,A survey of Zarankiewicz problem in geometry, preprint, arXiv:2410.03702
S. Smorodinsky,A survey of Zarankiewicz problem in geometry, preprint, arXiv:2410.03702. 4
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.