{"id":"ef5840e5-7652-42a3-8ec7-ae6e3cb8fac7","arxiv_id":"2608.04985","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every integer ℓ≥2, any (1−ε,t)-sparse n-vertex graph with at least C t^{1−1/ℓ} n^{1+1/ℓ} edges contains at least C' d^{2ℓ} induced copies of the even cycle C_{2ℓ}, where d is its average degree.","lead":"This paper proves that locally sparse graphs with enough edges must contain many induced even cycles of any fixed length. It gives a partial answer to a 2024 open problem in extremal graph theory on supersaturation of induced cycles.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.5 is false when t is not an integer; the proof of Theorem 1.2 silently assumes integer t and needs either a clarifying restriction or a rounding argument.","rationale":"I checked Lemma 2.4 carefully; the log-convexity, Hölder, and K-almost-regularity steps are correct, so the reader's identified weak point actually holds. The main gap I find is the unstated integrality of t in Lemma 2.5. The proof's extreme-point reduction to 'size-t sets' is invalid for real t, and the lemma is false in that case. This affects Lemma 2.6 and hence the chord union bound in Lemma 3.2. The central theorem is very likely salvageable by rounding t up to an integer, so the paper should be accepted only after this is fixed or the statement is clarified. No issue with the main homomorphism-counting structure otherwise.","tokens_in":9225,"tokens_out":59736,"duration_ms":590282,"concrete_test":"Re-verify Lemma 2.5 with t=5/2, ε=1/4, Γ=K_2 plus an isolated vertex (n=3), and u=v=(2/5,2/5,1/5). Direct computation gives u^T A_Γ u=8/25 > 1/4, contradicting the lemma's conclusion. If this computation is confirmed, Lemma 2.5 is false for non-integer t; the proof of Theorem 1.2 must restrict t to integers or be amended by rounding t up to an integer before applying the sparse bounds.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 2.5 (Section 2) claims that for any (1−ε,t)-sparse graph Γ and any nonnegative vectors u,v with entries ≤1/t and total mass ≤1, u^T A_Γ v ≤ ε. Its proof reduces to scaled indicators of size-t sets, which is only valid for integer t. For non-integer t the reduction fails, and the claim itself is false. Counterexample: take t=5/2, ε=1/4, Γ on vertices {1,2,3} with the single edge 12. Γ is (1−ε,t)-sparse because the only subsets of size ≥5/2 are {1,2,3}, and e({1,2,3},{1,2,3})=2≤(1/4)·9. Let u=v=(2/5,2/5,1/5); entries are ≤1/t=2/5 and sums are 1, but u^T A_Γ u=2·(2/5)^2=8/25>1/4. Thus Lemma 2.5 fails, and with it the chord-probability bound in Lemma 2.6 for non-integer t. Since Theorem 1.2 quantifies over 'some t' without an integrality condition, the proof as written does not cover real t. The intended convention in the K_{t,t} context is almost certainly integer t, so this is a fixable gap: either state t is a positive integer, or replace t by T=ceil(t) (absorbs constants) and re-run the argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves a supersaturation result for induced even cycles in extremely locally sparse graphs. For every integer ℓ≥2, it claims constants ε>0, C, C′>0 such that any n-vertex (1−ε,t)-sparse graph with at least C t^{1−1/ℓ} n^{1+1/ℓ} edges contains at least C′ d^{2ℓ} induced copies of C_{2ℓ}, where d is the average degree. The proof uses the Jiang–Yepremyan regularisation lemma to reduce to K-almost-regular subgraphs, then counts homomorphic copies of C_{2ℓ} in each subgraph. A new heavy-vertex estimate (Lemma 2.4) controls the probability that a random homomorphism creates a chord in Γ, and a union bound over nonconsecutive position pairs, together with Janzer's bound on non-injective homomorphisms, yields a positive proportion of induced cycles. The paper thereby partially resolves a problem of Ding, Gao, Liu, Luan, and Sun.","tokens_in":9561,"tokens_out":15507,"duration_ms":161792,"significance":"If correct, the result is a significant contribution to supersaturation in locally sparse graphs, complementing the existence theorem of Ding et al. with a polynomial-in-t lower bound on the number of induced even cycles. The heavy-vertex estimate in Lemma 2.4 is a genuinely new ingredient, and the proof is transparent and self-contained modulo standard external results (walk identities, Sidorenko's inequality, and the regularisation lemma). The main gap, concerning non-integer t, is local and fixable, and the theorem is likely correct in the integer regime that is standard in this literature.","major_comments":[{"comment":"Lemma 2.5 is false as stated for non-integer t. For t=5/2, ε=1/4, let Γ be the 3-vertex graph with the single edge {1,2}. Then Γ is (1−ε,t)-sparse: the only vertex subsets of size at least 5/2 are the full set, and e({1,2,3},{1,2,3})=2 ≤ (1/4)·9. Taking u=v=(2/5,2/5,1/5), the entries are at most 1/t=2/5 and the total mass is 1, but u^T A_Γ u = 2·(2/5)^2 = 8/25 > 1/4 = ε. The reduction to scaled indicators of size-t sets is only valid for integer t, so the lemma needs an integrality hypothesis or a different argument.","section":"Section 2, Lemma 2.5"},{"comment":"Because Theorem 1.2 quantifies over \"some t\" without an integrality condition, the failure of Lemma 2.5 for non-integer t propagates to the chord-probability bound of Lemma 2.6 and therefore to the proof of the main theorem as written. The proof should either explicitly restrict t to positive integers or give a rounding argument, for instance replacing t by T=⌈t⌉ and using T≤2t to absorb the extra factor in the edge-density threshold.","section":"Theorem 1.2 and Lemma 2.6"}],"minor_comments":[{"comment":"The direct consequence of the second part of Lemma 3.3 is ∑ d_i^{2ℓ} ≥ (1/(8ℓ)) d(Γ)^{2ℓ}, not 1/4^{2ℓ}; since 1/(8ℓ) is larger than 1/4^{2ℓ} for ℓ≥2, the weaker displayed bound is true, but the derivation should be corrected.","section":"Proof of Theorem 1.2, final display"},{"comment":"The sentence \"Therefore w^k_vv is log convex in terms of k\" is ambiguous; the proof establishes log-convexity of the sequence w^{2k}_vv in k, and the text should say so.","section":"Lemma 2.3 proof"},{"comment":"The number of nonconsecutive pairs of positions on a 2ℓ-cycle is ℓ(2ℓ−3), not (2ℓ)^2; the displayed upper bound (2ℓ)^2 is a harmless overcount, but stating the exact number would be clearer.","section":"Lemma 3.2"}],"recommendation":"major_revision","confidential_remarks":"The non-integer t issue is likely a convention mismatch; in the literature on (c,t)-sparse graphs, t is typically an integer. The authors should be asked to state the intended convention and adjust the statement of Theorem 1.2 accordingly. The paper otherwise appears sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves a real new result: supersaturation for induced C_{2ℓ} in (1−ε,t)-sparse graphs for every ℓ≥2, with polynomial dependence on t. The C4 case was known, so the advance is for ℓ≥3. The main technical innovation, the heavy-vertex mass bound in Lemma 2.4, looks legitimate, and the chain from there through Lemma 2.6 to the main theorem checks out as far as I can tell. This is a solid contribution to the induced Turán program, and the citations to Ding et al., Janzer, Jiang–Yepremyan, and the K_{s,s}-free work are appropriate.\n\nThe paper has one genuine soft spot that the authors missed. Lemma 2.5 claims u^T A_Γ v ≤ ε for entrywise ≤1/t subprobability vectors, but the proof's extreme-point argument only works when t is an integer. For non-integer t the claim is false: take t=5/2, ε=1/4, Γ on three vertices with a single edge. Γ is (3/4,5/2)-sparse because the only subsets of size ≥2.5 are the whole vertex set. Let u=v=(2/5,2/5,1/5); then u^T A_Γ u = 8/25 > 1/4, contradicting the lemma. So Theorem 1.2, which quantifies over 'some t' with t≥1, is not proven for real t without further argument. This is fixable: either restrict t to positive integers, or replace t by ⌈t⌉ and adjust constants, since a (1−ε,t)-sparse graph is also (1−ε,⌈t⌉)-sparse. But the fix needs to be written down.\n\nA smaller, harmless issue: in the proof of Theorem 1.2, Lemma 3.3 with s=2ℓ gives ∑ d_i^{2ℓ} ≥ d^{2ℓ}/(8ℓ), and the paper instead writes 1/4^{2ℓ}. The latter is weaker but still true, so it does not affect the argument.\n\nThe proof is honest about the restriction to very sparse graphs (ε = O(ℓ^{-2})), and the new spread-outness estimate is a genuinely useful idea beyond this specific application. The paper deserves a serious referee; the flaw is local and fixable, and the main theorem is likely to stand once the integrality issue is settled. I would send it to review with a request to address the t issue explicitly.\n\nFor a reader working in extremal graph theory, this is worth a look. I'd bring it to our reading group, and I'd cite it once the fix is in place.","headline":"Genuinely new supersaturation result for induced even cycles in locally sparse graphs, but the proof of Lemma 2.5 silently assumes integer t and the theorem as stated over real t is false without a rounding fix.","tokens_in":10155,"tokens_out":9116,"would_cite":true,"duration_ms":97462,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"Locally sparse graphs with sufficiently many edges must contain many induced copies of every fixed even cycle.","keywords":["induced even cycles","supersaturation","locally sparse graphs","(c,t)-sparse graphs","homomorphism counting","extremal graph theory","random walks in graphs"],"falsifier":"Compute the quantity $\\rho_r$ from Lemma 2.4 on a concrete family of almost-regular graphs at the threshold degree $d \\asymp t^{1-1/\\ell}n^{1/\\ell}$, for example random regular graphs, and check whether for some $\\ell$ and some choices of $x,y$ the total probability mass of vertices appearing at one internal position in at least $1/t$ of the $x,y$-walks exceeds $K(t^{\\ell-1}n/d^\\ell)^{1/(\\ell-1)}$; any such example would invalidate the key estimate and the proof of the theorem.","tokens_in":9030,"feed_emoji":"🔄","tokens_out":10995,"duration_ms":107080,"temperature":0.7,"pith_summary":"Extremal graph theory traditionally asks how many edges force a copy of a forbidden graph; for induced copies of an even cycle $C_{2\\ell}$, the question only makes sense under an extra sparsity condition, and this paper proves a quantitative supersaturation theorem in that setting. The main result states that for every fixed length $2\\ell$, there are constants depending only on $\\ell$ such that any $n$-vertex graph that is $(1-\\varepsilon,t)$-sparse — meaning that between any two vertex sets of size at least $t$, the edge count stays below $(1-\\varepsilon)$ times the product of the set sizes — and has at least $Ct^{1-1/\\ell}n^{1+1/\\ell}$ edges must contain at least $C'd^{2\\ell}$ induced copies of $C_{2\\ell}$, where $d$ is the average degree. At the stated edge threshold this is, up to constants, at least $C''t^{2\\ell-2}n^2$ copies, matching the polynomial dependence on $t$ conjectured for this problem. The proof counts homomorphic cycles and shows that almost all of them are genuine induced cycles, using a new estimate on the mass of vertices that appear very often at a fixed position along random walks.","feed_headline":"Enough edges in a locally sparse graph force many induced even cycles","feed_subtitle":"A fixed even cycle appears at least C·d^{2ℓ} times once edges pass the n^{1+1/ℓ} threshold","key_machinery":"The load-bearing object is the distribution of random walks along the cycle: for vertices $x,y$, let $w^\\ell_{xy}$ be the number of length-$\\ell$ walks from $x$ to $y$, so that $\\hom(C_{2\\ell},G)=\\sum_{x,y}(w^\\ell_{xy})^2$ and this is at least $d^{2\\ell}$ by a standard lower bound. At each internal position $r$ of a random length-$\\ell$ walk from $x$ to $y$, a vertex $v$ is called heavy if its conditional position-probability $p^r_{xy}(v)$ is at least $1/t$; the new quantitative ingredient, Lemma 2.4, bounds the averaged total probability mass of heavy vertices by $K(t^{\\ell-1}n/d^\\ell)^{1/(\\ell-1)}$ in every $K$-almost-regular graph, using a log-convexity property of closed-walk counts. Once heavy vertices are discarded, every remaining position distribution has entries bounded by $1/t$, so the $(1-\\varepsilon,t)$-sparseness, expressed through the bilinear form $u^\\intercal A_\\Gamma v$, bounds the probability that any fixed pair of nonconsecutive positions forms a chord. A union bound over the $O(\\ell^2)$ possible chords, a cited bound on non-injective homomorphisms, and a cited regularisation lemma complete the proof.","core_discovery":"The central discovery is that the induced-$C_{2\\ell}$ supersaturation threshold is governed by the same exponent $n^{1+1/\\ell}$ as the classical (non-induced) even-cycle extremal number, provided the host graph is locally sparse enough. Concretely, Theorem 1.2 asserts that for every $\\ell \\ge 2$ there exist $\\varepsilon > 0$, $C > 0$ and $C' > 0$ such that if $\\Gamma$ is $(1-\\varepsilon,t)$-sparse and has at least $Ct^{1-1/\\ell}n^{1+1/\\ell}$ edges, then $\\Gamma$ contains at least $C'd^{2\\ell}$ induced copies of $C_{2\\ell}$, where $d$ is its average degree. The argument regularises the host graph into edge-disjoint almost-regular pieces, counts homomorphisms of the even cycle in each piece via a walk-eigenvalue identity, and then uses the strong sparseness assumption to prove that only a small controlled fraction of those homomorphisms acquire a chord; summing over the pieces yields the bound for the original graph. This gives the first proof of the conjectured supersaturation statement in the 'bootstrapped' locally sparse regime and, combined with a known bootstrap lemma, an alternative route to the earlier induced Turán theorem for such graphs.","pith_inferences":["The theorem only operates in the extremely sparse regime $c=1-\\varepsilon$ with $\\varepsilon$ of order $\\ell^{-2}$; nothing in the proof rules out a threshold phenomenon where for some small fixed $c<1$ the polynomial dependence on $t$ fails or a counterexample exists, which would make the boundary of the phenomenon an interesting object in its own right.","Because the proof shows that a positive fraction of all homomorphic cycles are induced in $\\Gamma$, sampling random walks in a locally sparse graph above the threshold would find induced even cycles with positive probability, suggesting a simple randomised search procedure.","The heavy-vertex mass bound is stated for two walk halves of equal length between two endpoints; the same log-convexity mechanism may transfer to counting induced even paths or other bipartite configurations built from two long walks, giving future supersaturation results beyond exact even cycles."],"forward_implications":["Under the theorem's hypotheses, the number of induced $C_{2\\ell}$ copies is at least $C'd^{2\\ell}$, which is proportional to $t^{2\\ell-2}n^2$ when the edge count is at the stated threshold; this is the same polynomial dependence on $t$ conjectured in the original problem.","The result upgrades the earlier existence theorem for induced even cycles in locally sparse graphs to a quantitative counting statement in the $(1-\\varepsilon,t)$-sparse regime.","Together with the bootstrap lemma, the proof yields a new derivation of the induced Turán theorem for $(c,t)$-sparse graphs, because forbidding an induced $C_{2\\ell}$ pushes the graph into the regime where the new counting bound applies.","Because the count is established by summing over edge-disjoint almost-regular subgraphs without double counting, the lower bound is stable under the regularisation decomposition and holds for the whole host graph, not just for its regular pieces."],"supporting_citations":[{"why":"posed the supersaturation problem for induced even cycles in (c,t)-sparse graphs and proved the existence version that this paper extends.","marker":"[5]"},{"why":"introduced the (c,t)-sparse framework and the systematic study of induced Turán and supersaturation problems in it.","marker":"[10]"},{"why":"supplies the regularisation lemma that decomposes the host graph into edge-disjoint K-almost-regular pieces.","marker":"[13]"},{"why":"provides the bound on non-injective homomorphisms used to discard degenerate cycles.","marker":"[12]"},{"why":"gives the walk-eigenvalue identity expressing hom(C_{2ℓ},G) as the sum of (w^ℓ_xy)^2 over ordered vertex pairs.","marker":"[17]"},{"why":"yields the lower bound hom(C_{2ℓ},G) ≥ d^{2ℓ} for graphs of average degree d.","marker":"[16]"},{"why":"introduced the homomorphism-counting approach in the K_{s,s}-free induced Turán setting that the present proof adapts.","marker":"[11]"},{"why":"established a related supersaturation result for induced even cycles in dense almost-regular K_{s,s}-free graphs, providing context and a technique comparison.","marker":"[6]"}],"fun_headline_variants":["Edge surplus in locally sparse graphs forces induced even cycles","Locally sparse host graphs: edge excess yields induced even cycles","Supersaturation threshold for induced even cycles is n^{1+1/ℓ}","Many edges in locally sparse graphs force induced even cycles","Edge count above n^{1+1/ℓ} ensures many induced even cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the claim that in a nearly regular graph, the vertices appearing unusually often at a fixed spot along random walks between two endpoints cannot, in total, carry too much probability; if that bound fails, the step that rules out unwanted edges between nonconsecutive vertices of the cycle collapses.","fun_headline_variants_meta":{"raw":{"variants":["Edge surplus in locally sparse graphs forces induced even cycles","Locally sparse host graphs: edge excess yields induced even cycles","Supersaturation threshold for induced even cycles is n^{1+1/ℓ}","Many edges in locally sparse graphs force induced even cycles","Edge count above n^{1+1/ℓ} ensures many induced even cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001023,"raw_usage":{"total_tokens":4353,"prompt_tokens":1019,"completion_tokens":3334,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":635,"completion_tokens_details":{"reasoning_tokens":3243}},"tokens_in":635,"tokens_out":3334,"duration_ms":27065,"temperature":1.0,"reasoning_tokens":3243,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T12:11:27.933873+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the quantity $\\rho_r$ from Lemma 2.4 on a concrete family of almost-regular graphs at the threshold degree $d \\asymp t^{1-1/\\ell}n^{1/\\ell}$, for example random regular graphs, and check whether for some $\\ell$ and some choices of $x,y$ the total probability mass of vertices appearing at one internal position in at least $1/t$ of the $x,y$-walks exceeds $K(t^{\\ell-1}n/d^\\ell)^{1/(\\ell-1)}$; any such example would invalidate the key estimate and the proof of the theorem.","supporting_citations":[{"cited_title":"Induced even cycles in locally sparse graphs","cited_arxiv_id":"2411.12659","evidence_quote":"posed the supersaturation problem for induced even cycles in (c,t)-sparse graphs and proved the existence version that this paper extends."},{"cited_title":"The largest subgraph without a forbidden induced subgraph.Combinatorica, 45(6):60, 2025","cited_arxiv_id":null,"evidence_quote":"introduced the (c,t)-sparse framework and the systematic study of induced Turán and supersaturation problems in it."},{"cited_title":"Supersaturation of even linear cycles in linear hyper- graphs.Combinatorics, Probability and Computing, 29(5):698–721, 2020","cited_arxiv_id":null,"evidence_quote":"supplies the regularisation lemma that decomposes the host graph into edge-disjoint K-almost-regular pieces."},{"cited_title":"Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles","cited_arxiv_id":null,"evidence_quote":"provides the bound on non-injective homomorphisms used to discard degenerate cycles."},{"cited_title":"Undergraduate Texts in Mathematics","cited_arxiv_id":null,"evidence_quote":"gives the walk-eigenvalue identity expressing hom(C_{2ℓ},G) as the sum of (w^ℓ_xy)^2 over ordered vertex pairs."},{"cited_title":"Inequalities for functionals generated by bipartite graphs.Discrete math- ematics and applications, 2(5):489–504, 1992","cited_arxiv_id":null,"evidence_quote":"yields the lower bound hom(C_{2ℓ},G) ≥ d^{2ℓ} for graphs of average degree d."},{"cited_title":"Kővári-Sós-Turán theorem for hereditary families.Journal of Combinatorial Theory","cited_arxiv_id":null,"evidence_quote":"introduced the homomorphism-counting approach in the K_{s,s}-free induced Turán setting that the present proof adapts."}],"review_version":1}