{"id":"f348f2d5-71a2-4b5d-8deb-bb2daf7255f0","arxiv_id":"2607.06444","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Every K_{s,t}-free graph of average degree Ω(h^{2(s-1)} log^{7(s-1)} h) and every C_{2k}-free graph of average degree Ω(h log^5 h) contains an induced subdivision of K_h, both nearly optimal.","lead":"The paper proves nearly tight bounds on the average degree required to force an induced subdivision of a complete graph in sparse, cycle-free graphs. This resolves a quantitative gap in extremal graph theory, showing that K_{s,t}-free and C_{2k}-free graphs require only a polylogarithmic factor above the optimal degree.","discovery_kind":"first_principles","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified","rationale":"The reader correctly identified Lemma 4.5 and its forbidden-set density condition as the most load-bearing technical step. Having examined it carefully, the inductive argument is sound: the exponential growth of |A_i| (via e^{i^{1/3}/3}) ensures the expansion term dominates the polynomial-in-i forbidden-set terms, and the application in Lemma 4.6 verifies the required premises. The reader's verdict of ACCEPT with HIGH confidence is appropriate. The paper makes a substantial contribution with nearly tight bounds, the proofs are detailed and modular, and the new drifting-away path technique addresses a real gap in prior approaches (as noted in the footnote about Komlós-Szemerédi). The lower-bound constructions are well-matched to the upper bounds. No adjustment to the verdict is needed.","tokens_in":26875,"tokens_out":803,"duration_ms":450760,"concrete_test":"Independently verify the inductive step in Lemma 4.5 by checking that the inequality 1/(10 log^2(15|A_{i-1}|/r)) - 2(i+1)^3/(10^15 * |A_{i-1}|) - (Δ(G))^{i^{1/3}/(20 log Δ(G))}/(10^3 * |A_{i-1}|) >= 1/(13 log^2(15|A_{i-1}|/r)) holds for all i >= 1 given |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30, by substituting the lower bound on |A_{i-1}| and verifying the error terms are at most 1/(30 log^2(15|A_{i-1}|/r)) of the expansion term.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claims rest on a modular argument: a dichotomy (Lemma 3.1) reducing to either a highly irregular case (handled by Lemma 3.5 via reduction to classical subdivision results) or a nearly-regular case (handled by Lemma 4.6 via the drifting-away path Lemma 4.5). I carefully checked the most delicate step: the inductive growth bound in Lemma 4.5. The key inequality is |N(A_{i-1})| >= |A_{i-1}|/(10 log^2(15|A_{i-1}|/r)), and the forbidden-set subtraction removes at most 2r(i+1)^3/10^15 + r(Δ(G))^{i^{1/3}/(20 log Δ(G))}/10^3. The inductive hypothesis |A_{i-1}| >= r e^{(i-1)^{1/3}/3}/30 ensures the expansion term dominates the forbidden-set terms, since e^{(i-1)^{1/3}/3} grows faster than any polynomial in i. The product telescoping argument yielding log^3(15|A_i|/r) >= i/26 is correct. The application context in Lemma 4.6 verifies the premises of Lemma 4.5: the forbidden set F_q satisfies |B^(ℓ)(U_1 ∪ U_2) ∩ F_q| <= r + rℓ^3/10^15, which meets the required bound |F ∩ B^(ℓ)(U_1 ∪ U_2)| <= r(ℓ+1)^3/10^15. The reader's concern about this specific condition is well-placed as the most technical step, but the condition is verified in the application. The parameter choices in Theorems 1.1 and 1.2 are consistent with the lemma requirements. I found no internally inconsistent step or gap in the logical chain.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","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.","tokens_in":27178,"tokens_out":2297,"duration_ms":702836,"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":[{"comment":"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,","section":null},{"comment":"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,","section":null},{"comment":"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,","section":null}],"minor_comments":[{"comment":"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":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong submission with near-optimal results and a clean modular structure. The main technical lemma (Lemma 4.5) is the load-bearing piece; upon careful inspection the induction is sound, but the verification that the forbidden-set terms are dominated by the expansion term is the one place where a reader might want more detail. I recommend minor revision to address the presentation issues and add the missing justification in Lemma 4.5. The remark about a gap in [12] is handled responsibly and does not affect the correctness of the present paper."},"author_rebuttal":{"model":"glm-5.2","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"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."}],"tokens_in":27323,"tokens_out":976,"duration_ms":63873,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"Bottom line: this paper essentially resolves the quantitative question of when induced subdivisions of K_h must appear in K_{s,t}-free and C_{2k}-free graphs, up to polylogarithmic factors. The bounds are nearly optimal and the proofs are solid. It deserves a serious referee and a strong recommendation for acceptance at a top combinatorics venue.","headline":"Nearly tight bounds for induced subdivisions — a genuine advance with clean, modular proofs.","tokens_in":27673,"tokens_out":127,"would_cite":true,"duration_ms":81325,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05D40","05C10","05C83"],"pacs":[],"model":"glm-5.2","headline":"Induced clique subdivisions found at nearly optimal degree","keywords":["induced subdivision","K_{s,t}-free graphs","C_{2k}-free graphs","sublinear expanders","drifting-away paths","average degree","extremal graph theory"],"falsifier":"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.","tokens_in":27002,"feed_emoji":"🕸️","tokens_out":864,"duration_ms":119237,"temperature":0.7,"pith_summary":"The paper proves nearly tight bounds on how large the average degree of a graph must be to guarantee an induced subdivision of a complete graph K_h, in two natural sparse settings: graphs forbidding K_{s,t} and graphs forbidding even cycles C_{2k}. The central mechanism is a two-case dichotomy: either the graph is highly irregular (very unbalanced bipartite), in which case the problem reduces to the classical non-induced subdivision theorem of Bollobás–Thomason and Komlós–Szemerédi via an auxiliary graph; or the graph is nearly regular, in which case the authors find the induced subdivision directly using sublinear expansion. In the nearly-regular case, a key innovation is the notion of a drifting-away path — a path whose vertices move away from the branch vertices at a controlled rate — which prevents connecting paths from exhausting the neighborhoods of the branch vertices. For K_{s,t}-free graphs, the bound is Ω(h^{2(s−1)} log^{7(s−1)} h), nearly matching a random-construction lower bound. For C_{2k}-free graphs, the bound is Ω(h log^5 h), optimal up to the logarithmic factor since average degree h is necessary.","feed_headline":"Nearly tight degree thresholds for induced clique subdivisions","feed_subtitle":"New bounds on average degree forcing induced subdivisions of complete graphs are optimal up to logarithmic factors in two key sparse graph","key_machinery":"drifting-away path","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Degree thresholds for induced clique subdivisions nearly resolved","Near-optimal bounds for induced subdivisions in sparse graphs","Drifting-away paths yield nearly tight induced subdivision bounds","Forcing induced subdivisions: nearly tight degree thresholds","Induced clique subdivisions appear at near-optimal degree thresholds"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Degree thresholds for induced clique subdivisions nearly resolved","Near-optimal bounds for induced subdivisions in sparse graphs","Drifting-away paths yield nearly tight induced subdivision bounds","Forcing induced subdivisions: nearly tight degree thresholds","Induced clique subdivisions appear at near-optimal degree thresholds"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":649,"prompt_tokens":576,"completion_tokens":73,"prompt_tokens_details":null},"tokens_in":576,"tokens_out":73,"duration_ms":27444,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T05:31:48.193440+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"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.","supporting_citations":[],"review_version":1}