Pith. sign in

REVIEW 2 major objections 3 minor 18 references

Supersaturation of induced even cycles in locally sparse graphs

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Locally sparse graphs with sufficiently many edges must contain many induced copies of every fixed even cycle.

desk verdict 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. read the letter →

arxiv 2608.04985 v1 pith:XN4I2SA4 submitted 2026-08-05 math.CO

Adam Džavoronok , Ole Gabsdil , Alexander Mylet , Maria-Cristina Popa , Yinghan Andie Shao This is my paper
classification math.CO MSC 05C3505C38
keywords inducedevencyclessupersaturationlocallysparsegraphs(ct)-sparsehomomorphismcountingextremalgraphtheoryrandomwalksin
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [Section 2, Lemma 2.5] 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.
  2. [Theorem 1.2 and Lemma 2.6] 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.
minor comments (3)
  1. [Proof of Theorem 1.2, final display] 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.
  2. [Lemma 2.3 proof] 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.
  3. [Lemma 3.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof derives the supersaturation bound from stated hypotheses via external lemmas and a new heavy-vertex estimate, with no fitted input renamed as prediction.

full rationale

The paper's derivation of Theorem 1.2 does not reduce to its own inputs. The proof splits the sparse graph into K-almost-regular subgraphs using Jiang and Yepremyan (Lemma 3.3), lower-bounds hom(C_{2ℓ}, G) using Sidorenko and the spectral walk identity (Lemmas 2.1 and 2.2), bounds non-injective homomorphisms using Janzer's lemma (Lemma 3.1), and bounds chord probabilities using the new heavy-vertex mass estimate (Lemma 2.4) together with the bilinear-form sparse bound (Lemma 2.5). All constants C, C′, and ε are chosen explicitly from ℓ and K, never fitted to the induced-cycle count. The two failure modes (non-injectivity and chords) are each bounded below 1/4 of hom(C_{2ℓ}, G) by taking C1 large, leaving at least (1/(8ℓ)) d^{2ℓ} induced copies, which is then summed over edge-disjoint subgraphs. The cited result of Ding et al. (Lemma 1.3) appears only in a concluding remark about an alternative route to the induced Turán theorem and is not load-bearing for Theorem 1.2. There are no self-citations of the present authors, and the external lemmas are independent published results. The potential non-integrality of t in Lemma 2.5's proof would be a correctness gap, not circularity: it does not make the target count equal to an input by construction. Thus no circular step can be exhibited under the hard rules; the score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proof introduces no empirical free parameters or new entities. The constants ε, C, C', C_0, C_1, K are existential and chosen in the proof; they are not fitted to data. The central claim rests on standard external lemmas (walk-count identities, Sidorenko inequality, Janzer's homomorphism bound, Jiang-Yepremyan regularization) and on the implicit convention that t is a positive integer. No circular self-reference occurs: the theorem is not used in its own proof, and the cited existence result of Ding et al. appears only in a side remark.

assumptions (6)
  • standard math hom(C_{2ℓ}, G) ≥ d^{2ℓ} for any n-vertex graph G with average degree d (Lemma 2.2, Sidorenko).
    Used to lower-bound the number of homomorphic even cycles; a well-known result cited to [16].
  • standard math Spectral identities for closed walks: hom(C_{2ℓ}, G) = ∑ λ_i^{2ℓ} = ∑_{x,y} (w^ℓ_{xy})^2 (Lemma 2.1).
    Standard linear algebra; cited to [17].
  • domain assumption Janzer's bound on homomorphisms with repeated vertices (Lemma 3.1, from [12]).
    External result used to control non-injective homomorphisms; not proved in the paper.
  • domain assumption Jiang-Yepremyan regularization lemma (Lemma 3.3, from [13]) asserting existence of edge-disjoint K-almost-regular subgraphs with f-weighted sum lower bound.
    External decomposition result; load-bearing for summing over subgraphs.
  • domain assumption Lemma 1.3 (Lemma 3.1, [5]): if a (c,t)-sparse graph has no induced H, then it is (1−ε, βt)-sparse for large β.
    Used only in the concluding remark to derive an alternative proof of the existence theorem; not used in the proof of Theorem 1.2.
  • domain assumption t is a positive integer (implicit in the definition of (c,t)-sparse).
    The extreme-point argument in Lemma 2.5 selects the 't largest coordinates', which requires t to be an integer; the paper does not state this explicitly.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Supersaturation of induced even cycles in locally sparse graphs." pith.science (2026). https://pith.science/paper/XN4I2SA4

@misc{pith2026260804985,
  author       = {Pith},
  title        = {Pith review of: Supersaturation of induced even cycles in locally sparse graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XN4I2SA4}},
  note         = {Machine review of arXiv:2608.04985}
}
abstract

A graph $\Gamma$ is $(c,t)$-sparse for $c > 0$ and $t \ge 1$ if for every pair of vertex subsets $A, B \subseteq V(\Gamma)$ with $|A|, |B| \ge t$, the number of edges $e(A,B)$ between them satisfies $ e(A,B) \le (1 - c)|A||B|$. In this paper, we prove that for every integer $\ell\ge2$, there are $\varepsilon > 0, C, C' > 0$ such that if an $n$-vertex graph $\Gamma$ is $(1-\varepsilon,t)$-sparse for some $t$, and has at least $Ct^{1-1/\ell}n^{1+1/\ell}$ edges, then $\Gamma$ contains at least $C'n^2t^{2\ell-2}$ induced copies of $C_{2\ell}$. This partially resolves a problem of Ding, Gao, Liu, Luan, and Sun.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

  1. [1]

    Induced Turán problem in bipartite graphs.Discrete Applied Mathematics, 360:497–505, 2025

    Maria Axenovich and Jakob Zimmermann. Induced Turán problem in bipartite graphs.Discrete Applied Mathematics, 360:497–505, 2025. ISSN 0166-218X

    work page 2025

  2. [2]

    Degeneracy ofPt-free andC ≥t-free graphs with no large complete bipartite subgraphs.Journal of Combinatorial Theory

    MartheBonamy, NicolasBousquet, MichałPilipczuk, PawełRzążewski, StéphanThomassé, and Bartosz Walczak. Degeneracy ofPt-free andC ≥t-free graphs with no large complete bipartite subgraphs.Journal of Combinatorial Theory. Series B, 152:353–378, 2022. ISSN 0095-8956

    work page 2022

  3. [3]

    Cycles of even length in graphs.Journal of Combinatorial Theory, Series B, 16(2):97–105, 1974

    John Adrian Bondy and Miklós Simonovits. Cycles of even length in graphs.Journal of Combinatorial Theory, Series B, 16(2):97–105, 1974. doi: 10.1016/0095-8956(74)90052-5

    doi:10.1016/0095-8956(74)90052-5 1974

  4. [4]

    On polynomial degree- boundedness.Advances in Combinatorics (Online), 2024

    Romain Bourneuf, Matija Bucić, Linda Cook, and James Davies. On polynomial degree- boundedness.Advances in Combinatorics (Online), 2024. ISSN 2517-5599

    work page 2024

  5. [5]

    Induced even cycles in locally sparse graphs

    Laihao Ding, Jun Gao, Hong Liu, Bingyu Luan, and Shumin Sun. Induced even cycles in locally sparse graphs.arXiv preprint arXiv:2411.12659, 2024

    work page Pith review arXiv 2024

  6. [6]

    Induced rational exponents and bipartite subgraphs inK s,s-free graphs.arXiv preprint arXiv:2506.09020, 2025

    Zichao Dong, Jun Gao, Ruonan Li, and Hong Liu. Induced rational exponents and bipartite subgraphs inK s,s-free graphs.arXiv preprint arXiv:2506.09020, 2025

    arXiv 2025

  7. [7]

    Erdős and M

    P. Erdős and M. Simonovits. A limit theorem in graph theory.Studia Scientiarum Mathem- aticarum Hungarica, 1:51–57, 1966. ISSN 0081-6906

    work page 1966

  8. [8]

    Erdős and M

    P. Erdős and M. Simonovits. Cube-supersaturated graphs and related problems. In J. A. Bondy and U. S. R. Murty, editors,Progress in Graph Theory (Waterloo, Ont., 1982), pages 203–218. Academic Press, Toronto, ON, 1984

    work page 1982

Show all 18 references
  1. [9]

    Erdős and A

    P. Erdős and A. H. Stone. On the structure of linear graphs.Bulletin of the American Mathem- atical Society, 52(12):1087–1091, 1946. ISSN0002-9904. doi: 10.1090/S0002-9904-1946-08715-7. 10 DŽA VORONOK, GABSDIL, MYLET, POPA, AND SHAO

    1946 doi

  2. [10]

    The largest subgraph without a forbidden induced subgraph.Combinatorica, 45(6):60, 2025

    Jacob Fox, Rajko Nenadov, and Huy Tuan Pham. The largest subgraph without a forbidden induced subgraph.Combinatorica, 45(6):60, 2025. doi: 10.1007/s00493-025-00190-y

    2025 doi

  3. [11]

    Kővári-Sós-Turán theorem for hereditary families.Journal of Combinatorial Theory

    Zach Hunter, Aleksa Milojević, Benny Sudakov, and István Tomon. Kővári-Sós-Turán theorem for hereditary families.Journal of Combinatorial Theory. Series B, 172:168–197, 2025. ISSN 0095-8956

    2025

  4. [12]

    Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles

    Oliver Janzer. Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles. Israel Journal of Mathematics, 253(2):813–840, 2023. ISSN 0021-2172

    2023

  5. [13]

    Supersaturation of even linear cycles in linear hyper- graphs.Combinatorics, Probability and Computing, 29(5):698–721, 2020

    Tao Jiang and Liana Yepremyan. Supersaturation of even linear cycles in linear hyper- graphs.Combinatorics, Probability and Computing, 29(5):698–721, 2020. doi: 10.1017/ S0963548320000206

    2020

  6. [14]

    Induced subdivisions inK s,s-free graphs of large average degree.Combinatorica, 24(2):287–304, 2004

    Daniela Kühn and Deryk Osthus. Induced subdivisions inK s,s-free graphs of large average degree.Combinatorica, 24(2):287–304, 2004. ISSN 0209-9683

    2004

  7. [15]

    Po-Shen Loh, Michael Tait, Craig Timmons, and Rodrigo M. Zhou. Induced Turán numbers. Combinatorics, Probability & Computing, 27(2):274–288, 2018. ISSN 0963-5483

    2018

  8. [16]

    Inequalities for functionals generated by bipartite graphs.Discrete math- ematics and applications, 2(5):489–504, 1992

    Alexander Sidorenko. Inequalities for functionals generated by bipartite graphs.Discrete math- ematics and applications, 2(5):489–504, 1992. ISSN 0924-9265

    1992

  9. [17]

    Undergraduate Texts in Mathematics

    Richard P Stanley.Algebraic Combinatorics: Walks, Trees, Tableaux, and More. Undergraduate Texts in Mathematics. Springer Nature, New York, 2013 edition, 2013. ISBN 1461469988

    2013

  10. [18]

    Extremal graphs with noC 4’s,C 6’s, orC 10’s.Journal of Combinatorial Theory, Series B, 52(1):113–116, 1991

    Rephael Wenger. Extremal graphs with noC 4’s,C 6’s, orC 10’s.Journal of Combinatorial Theory, Series B, 52(1):113–116, 1991. doi: 10.1016/0095-8956(91)90097-4. Department of Applied Mathematics, Charles University, F aculty of Mathematics and Physics, Malostranské nám. 25, 118...

    1991 doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.