REVIEW 3 major objections 6 minor 23 references
Nearly tight bounds for induced subdivisions
T0 review · 3 major / 6 minor · reviewed 2026-07-08 · glm-5.2
Pith's one-line read Induced clique subdivisions found at nearly optimal degree
desk verdict Nearly tight bounds for induced subdivisions — a genuine advance with clean, modular proofs. 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
drifting-away path
What would settle it
A K_{s,t}-free or C_{2k}-free graph with average degree exceeding the stated thresholds but containing no induced subdivision of K_h.
Extended reading notes
Core claim
The authors introduce drifting-away paths within the sublinear expander framework to build induced subdivisions directly, rather than reducing to the non-induced problem. This, combined with a structural dichotomy separating highly irregular graphs from nearly regular ones, yields bounds within polylogarithmic factors of optimal in both the K_{s,t}-free and C_{2k}-free settings.
Load-bearing premise
The drifting-away path lemma requires that the forbidden set's local density satisfies a specific bound (|F ∩ B^(ℓ)(U_1 ∪ U_2)| ≤ r(ℓ+1)^3/10^15) at each scale; if this bound fails in the application context, the connecting paths cannot be found.
Editorial extensions
If this is right
- The gap between the upper bound (h^2 polylog h) and the lower bound (h^{4/3}) for C_4-free graphs leaves open the true threshold for induced subdivisions in C_4-free graphs, which the authors identify as a key open problem.
- The drifting-away path technique may be applicable to other induced embedding problems where connecting paths must avoid accumulated neighborhoods of previously embedded structures.
- The dichotomy between highly irregular and nearly regular graphs provides a template that could be adapted to other extremal problems in sparse graph classes.
- Removing the polylogarithmic factors from both theorems would yield fully tight results, which the authors identify as an interesting direction.
Reading between the lines
- The bound for C_{2k}-free graphs (h log^5 h) is likely closer to optimal than the bound for K_{s,t}-free graphs, since the lower bound in the latter case has a polynomial gap. This suggests the K_{s,t}-free lower bound may be improvable with more refined constructions.
- The log^5 h factor in the C_{2k}-free case likely arises from the interplay between the path length O(log^3 h) guaranteed by sublinear expansion and the size of the forbidden set, suggesting that tighter path-length bounds could reduce the exponent.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the average degree threshold needed to force an induced subdivision of K_h (or any h-vertex graph H) in two natural sparse settings: K_{s,t}-free graphs and C_{2k}-free graphs. The main results (Theorems 1.1 and 1.2) establish bounds of Ω_{s,t}(h^{2(s-1)} log^{7(s-1)} h) and Ω_k(h log^5 h) respectively, which are nearly tight up to polylogarithmic factors. The proof proceeds via a structural dichotomy (Lemma 3.1) splitting into a highly irregular case, handled by reduction to the classical Bollobás–Thomason / Komlós–Szemerédi theorem, and a nearly-regular case, handled via a novel 'drifting-away path' lemma (Lemma 4.5) in the sublinear expander framework. Lower bounds come from standard random graph constructions and polarity graphs.
Significance. The paper makes a substantial contribution to the study of induced subdivisions, substantially improving the previously known quantitative bounds of Kühn–Osthus and subsequent works. The near-optimality of the bounds in both the K_{s,t}-free and C_{2k}-free settings is a notable strength. The key technical innovation is the notion of 'drifting-away paths' (Definition 4.4) and the associated Lemma 4.5, which provides a unified approach to the nearly-regular case regardless of whether n is polynomial in h. The lower-bound constructions are standard but correctly applied and clearly explained. The modular proof structure is a strength, making the argument auditable.
major comments (3)
- Lemma 4.5, proof: In the inductive step, the expansion lower bound is stated as |N(A_{i-1})| >= |A_{i-1}| / (10 log^2(15|A_{i-1}|/r)). The subsequent subtraction of the forbidden-set terms yields a denominator of 13 log^2(15|A_{i-1}|/r). The telescoping product then uses 1/(13 log^2(15|A_i|/r)) to derive log^3(15|A_i|/r) >= i/26. This chain of inequalities is correct, but the jump from the 1/10 factor to 1/13 is stated without an explicit intermediate calculation showing that the two subtracted terms (2r(i+1)^3/10^15 and r(Δ(G))^{i^{1/3}/(20 log Δ(G))}/10^3) are each bounded by, say, |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)). The inductive hypothesis |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30 is invoked, but the reader must verify that e^{(i-1)^{1/3}/3} dominates (i+1)^3 and (Δ(G))^{i^{1/3}/(20 log Δ(G))} simultaneously. While this domination holds (the exponential in i^{1/3} outgrows any polynomial,
- Lemma 4.5, proof: In the inductive step, the expansion lower bound is stated as |N(A_{i-1})| >= |A_{i-1}| / (10 log^2(15|A_{i-1}|/r)). The subsequent subtraction of the forbidden-set terms yields a denominator of 13 log^2(15|A_{i-1}|/r). The telescoping product then uses 1/(13 log^2(15|A_i|/r)) to derive log^3(15|A_i|/r) >= i/26. This chain of inequalities is correct, but the jump from the 1/10 factor to 1/13 is stated without an explicit intermediate calculation showing that the two subtracted terms (2r(i+1)^3/10^15 and r(Δ(G))^{i^{1/3}/(20 log Δ(G))}/10^3) are each bounded by, say, |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)). The inductive hypothesis |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30 is invoked, but the reader must verify that e^{(i-1)^{1/3}/3} dominates (i+1)^3 and (Δ(G))^{i^{1/3}/(20 log Δ(G))} simultaneously. While this domination holds (the exponential in i^{1/3} outgrows any polynomial,
- Lemma 4.5, proof: In the inductive step, the expansion lower bound is stated as |N(A_{i-1})| >= |A_{i-1}| / (10 log^2(15|A_{i-1}|/r)). The subsequent subtraction of the forbidden-set terms yields a denominator of 13 log^2(15|A_{i-1}|/r). The telescoping product then uses 1/(13 log^2(15|A_i|/r)) to derive log^3(15|A_i|/r) >= i/26. This chain of inequalities is correct, but the jump from the 1/10 factor to 1/13 is stated without an explicit intermediate calculation showing that the two subtracted terms (2r(i+1)^3/10^15 and r(Δ(G))^{i^{1/3}/(20 log Δ(G))}/10^3) are each bounded by, say, |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)). The inductive hypothesis |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30 is invoked, but the reader must verify that e^{(i-1)^{1/3}/3} dominates (i+1)^3 and (Δ(G))^{i^{1/3}/(20 log Δ(G))} simultaneously. While this domination holds (the exponential in i^{1/3} outgrows any polynomial,
minor comments (6)
- Footnote 1 on page 3: The authors note a gap in the Komlós–Szemerédi paper [12]. While this is a useful remark, the phrasing 'we believe to be a gap' is somewhat informal for a journal article. Consider rephrasing to state the issue more directly, e.g., 'the inequality ⌈p/L⌉ ≤ 2p/L used in Section 3.3 of [12] requires L ≤ 2p, which need not hold in general.'
- Section 2, proof outline: The sketch mentions 'balls of radius 2 around them are disjoint and form induced trees with Ω(d^2) leaves. It is not the exact picture but is close enough to the truth for this sketch.' The parenthetical disclaimer is honest but slightly unusual; a brief parenthetical clarifying what the exact picture is (or a forward reference to Lemma 4.7) would help the reader.
- Lemma 3.5, Case 1: The independent set I ⊆ N is stated to have size at least 10^6 s^2 h^2, derived via Kővári–Sós–Turán. The computation uses α(G[N]) ≥ |N|/(d(G[N])+1), but the KST bound on d(G[N]) is stated as 2t^{1/(s-1)}|N|^{1-1/(s-1)}. The factor of 2 and the precise constant in the final bound should be checked for consistency, as the chain of inequalities is somewhat compressed.
- Lemma 4.1: The parameter p is set to 1/(5Kt d^{1-1/(s-1)} log d), but later in the proof the bound pn ≥ Ω(d^{1/(s-1)}/log d) is used. The dependence on K and t is dropped in this lower bound on pn; this is fine since K, t are constants, but making this explicit would avoid confusion.
- Proof of Theorem 1.1 (page 17): The average degree is stated as d = d(G) ≥ C t^{s-1} h^{2(s-1)} log^{7(s-1)} d. The logarithmic factor is log^{7(s-1)} d (i.e., in d, not h). The theorem statement (Theorem 1.1) uses log^{7(s-1)} h. Since d ≥ Ω(h^{2(s-1)} polylog h), log d = Θ(log h), so these are equivalent, but the switch between log h and log d throughout the paper should be made consistent or explicitly noted.
- Claim 4.10 proof: The set D_j is defined as {x ∈ V(G') ∖ B^{(2)}(v_j) : |N_{G'}(x) ∩ N^{(2)}(v_j)| ≥ 4k}, and the bound |D_j| ≤ |N^{(2)}(v_j)| ≤ Δ(G)^2 is stated. The justification via P_{4k-1}-freeness is correct, but the inequality |D_j| ≤ |N^{(2)}(v_j)| does not follow from the P_{4k-1} argument alone; rather, the P_{4k-1} argument gives |D_j| ≤ |N^{(2)}(v_j)|/(4k-1) or similar. Clarify the exact bound being used.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the positive assessment. The referee raises a single substantive point (repeated three times, apparently due to a copy-paste artifact), concerning the justification of the step in Lemma 4.5 where the expansion denominator changes from 10 log^2 to 13 log^2. We agree that the intermediate calculation should be made explicit and will add it to the revised manuscript.
read point-by-point responses
-
Referee: Lemma 4.5, proof: In the inductive step, the expansion lower bound is stated as |N(A_{i-1})| >= |A_{i-1}| / (10 log^2(15|A_{i-1}|/r)). The subsequent subtraction of the forbidden-set terms yields a denominator of 13 log^2(15|A_{i-1}|/r). [...] the jump from the 1/10 factor to 1/13 is stated without an explicit intermediate calculation showing that the two subtracted terms [...] are each bounded by, say, |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)). The inductive hypothesis |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30 is invoked, but the reader must verify that e^{(i-1)^{1/3}/3} dominates (i+1)^3 and (Δ(G))^{i^{1/3}/(20 log Δ(G))} simultaneously.
Authors: We agree with the referee that this step should be made explicit. The argument is as follows. By the inductive hypothesis, |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30. We need to show that each of the two subtracted terms is at most |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)), which would justify replacing 10 by 13 in the denominator (since 1/10 - 1/60 - 1/60 = 1/15 > 1/13, and we use 13 for a clean constant). For the first term: 2r(i+1)^3/10^{15} <= |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)) reduces (after substituting the inductive hypothesis and using log^2(15|A_{i-1}|/r) <= log^2(15n/r), which is bounded by a constant depending on the parameters) to showing e^{(i-1)^{1/3}/3} >= C(i+1)^3 for a suitable absolute constant C, which holds for all i >= 1 since the exponential in i^{1/3} dominates any polynomial. For the second term: r(Δ(G))^{i^{1/3}/(20 log Δ(G))}/10^3 <= |A_{i-1}|/(60 log^2(15|A_{i-1}|/r)) reduces to showing e^{(i-1)^{1/3}/3} >= C · (Δ(G))^{i^{1/3}/(20 log Δ(G))} = C · e^{i^{1/3}/20}, which holds since (i-1)^{1/3}/3 > i^{1/3}/20 for all i >= 1 (as 1/3 > 1/20). We will add these explicit calculations to the proof of Lemma 4.5 in the revised manuscript. revision: yes
Circularity Check
No significant circularity found
full rationale
The paper's derivation chain is self-contained against external benchmarks. The upper bounds rely on the classical Bollobás–Thomason / Komlós–Szemerédi theorem (Theorem 3.4, cited as [2, 12]) and the Kővári–Sós–Turán theorem, both external results. The sublinear expander framework (Definition 4.2, Theorem 4.3) is attributed to Komlós and Szemerédi [12]. The lower bounds are derived from standard random graph constructions (G(n,p)) and polarity graphs over F_q, not from the authors' own definitions. Self-citations ([6,7,8,10]) are used for context, motivation, and prior results, but the central claims of Theorems 1.1 and 1.2 are proved via a modular argument (dichotomy Lemma 3.1, highly irregular case Lemma 3.5, nearly-regular case Lemmas 4.5–4.8) that does not reduce to any self-cited result by construction. The drifting-away path lemma (Lemma 4.5) is a new technical contribution whose inductive growth bound is verified internally, and its premises are checked in the application context (Lemma 4.6). No step was found where a 'prediction' or 'first-principles result' is equivalent to its inputs by definition or by a fitted parameter renamed as a prediction. The dichotomy lemma (Lemma 3.1) was communicated by Girão and refines variants in [5,7], but it is proved from scratch in the paper (via Lemma 3.2 and Lemma 3.3) and is not load-bearing on any unverified self-citation. No circularity is present.
Assumptions & free parameters
assumptions (3)
- standard math Bollobás-Thomason / Komlós-Szemerédi theorem: graphs of average degree Ω(h^2) contain a subdivision of K_h.
- standard math Kővári-Sós-Turán theorem: K_{s,t}-free graphs have O(n^{2-1/s}) edges.
- standard math Komlós-Szemerédi sublinear expander theorem (Theorem 4.3): every graph contains a sublinear expander subgraph with roughly the same average degree.
invented entities (1)
-
Drifting-away path (Definition 4.4)
independent evidence
Cite this review
Pith. "Pith review of Nearly tight bounds for induced subdivisions." pith.science (2026). https://pith.science/paper/6ETDTSJG
@misc{pith2026260706444,
author = {Pith},
title = {Pith review of: Nearly tight bounds for induced subdivisions},
year = {2026},
howpublished = {\url{https://pith.science/paper/6ETDTSJG}},
note = {Machine review of arXiv:2607.06444}
}
abstract
Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conjecture of Mader, proved independently by Bollob\'as and Thomason and by Koml\'os and Szemer\'edi, states that every graph of average degree of order $h^2$ contains a subdivision of $K_h$. In this paper, we consider the induced variant of this problem. A theorem of K\"uhn and Osthus implies that, for every fixed graph $H$ and every $s\ge 1$, graphs of sufficiently large average degree contain either a copy of $K_{s,s}$ or an induced subdivision of $H$. However, even for $H=K_h$, the best previous quantitative bounds were far from optimal. We prove nearly tight bounds for forcing induced subdivisions of $K_h$. We show that every $K_{s,t}$-free graph of average degree $\Omega_{s,t}(h^{2(s-1)}\log^{7(s-1)} h)$ contains an induced subdivision of $K_h$, and that every $C_{2k}$-free graph with $k \geq 3$ and average degree $\Omega_k(h\log^5 h)$ contains an induced subdivision of $K_h$. These bounds substantially improve the previously known results and are nearly optimal in both settings. They also hold if $K_h$ is replaced by any other graph on $h$ vertices.
Reference graph
Works this paper leans on
- [1]
-
[2]
B. Bollobás and A. Thomason, Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs,European Journal of Combinatorics19 (1998), 883–887
work page 1998
- [3]
-
[4]
J. A. Bondy and M. Simonovits, Cycles of even length in graphs,J. Combin. Theory, Ser. B16 (1974), 97–105
work page 1974
-
[5]
R. Bourneuf, M. Bucić, L. Cook, and J. Davies, On polynomial degree-boundedness,Adv. Comb. (2024)
work page 2024
-
[6]
X. Du, A. Girão, Z. Hunter, R. McCarty and A. Scott, InducedC4-free subgraphs with large average degree,Journal of Combinatorial Theory, Series B173 (2025), 305–328
work page 2025
-
[7]
A. Girão and Z. Hunter, Induced subdivisions inKs,s-free graphs with polynomial average degree, International Mathematics Research Notices2025 (2025), Article ID rnaf025
work page 2025
-
[8]
A. Girão and Z. Hunter, Induced subdivisions ofK d+1 in graphs of high girth,preprint, arXiv:2603.09521
Show all 23 references
-
[9]
Gyárfás, On Ramsey covering-numbers.Colloquia Mathematica Societatis János Bolyai 10, Infinite and Finite Sets.North-Holland/American Elsevier, New York (1975), 801–816
A. Gyárfás, On Ramsey covering-numbers.Colloquia Mathematica Societatis János Bolyai 10, Infinite and Finite Sets.North-Holland/American Elsevier, New York (1975), 801–816
1975
-
[10]
Hunter, A
Z. Hunter, A. Milojević, B. Sudakov, I. Tomon,C4-free subgraphs of high degree with geometric applicationspreprint, arXiv:2506.23942
-
[11]
Janson, T
S. Janson, T. Łuczak and A. Ruciński,Random Graphs, Wiley-Interscience, New York, 2000
2000
-
[12]
Komlós and E
J. Komlós and E. Szemerédi, Topological cliques in graphs II,Combinatorics, Probability and Computing5 (1996), 79–90
1996
-
[13]
Kühn and D
D. Kühn and D. Osthus, Topological minors in graphs of large girth,Journal of Combinatorial Theory, Series B86 (2002), 364–380
2002
-
[14]
Kühn and D
D. Kühn and D. Osthus, Large topological cliques in graphs without a4-cycle,Combinatorics, Probability and Computing13 (2004), 93–102
2004
-
[15]
Kühn and D
D. Kühn and D. Osthus, Induced subdivisions inKs,s-free graphs of large average degree,Combi- natorica24 (2004), 287–304
2004
-
[16]
Kühn and D
D. Kühn and D. Osthus, Extremal connectivity for topological cliques in bipartite graphs,Journal of Combinatorial Theory, Series B96 (2006), 73–99
2006
-
[17]
Kühn and D
D. Kühn and D. Osthus, Improved bounds for topological cliques in graphs of large girth,SIAM Journal on Discrete Mathematics20 (2006), 62–78
2006
-
[18]
Liu and R
H. Liu and R. Montgomery, A proof of Mader’s conjecture on large clique subdivisions inC4-free graphs,Journal of the London Mathematical Society95 (2017), 203–222
2017
-
[19]
Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen.Math
W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen.Math. Ann.174 (1967) 265–268
1967
-
[20]
Mader, An extremal problem for subdivisions ofK− 5 .J
W. Mader, An extremal problem for subdivisions ofK− 5 .J. Graph Theory30 (1999), 261–276
1999
-
[21]
Nguyen, A
T. Nguyen, A. Scott and P. Seymour, Subdivisions and near-linear stable sets,Combinatorica45 (2025), no. 4, Paper No. 39
2025
-
[22]
Pawlik, J
A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter and B. Walczak, Triangle-free intersection graphs of line segments with large chromatic number,Journal of Combinatorial Theory, Series B105 (2014), 6–10
2014
-
[23]
D. P. Sumner, Subtrees of a graph and chromatic number.The Theory and Applications of Graphs, John Wiley & Sons, New York (1981) 557–576. 19
1981
Reviewed July 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.