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.
Induced even cycles in locally sparse graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
A graph $G$ is $(c,t)$-sparse if for every pair of vertex subsets $A,B\subset V(G)$ with $|A|,|B|\geq t$, $e(A,B)\leq (1-c)|A||B|$. In this paper we prove that for every $c>0$ and integer $\ell$, there exists $C>1$ such that if an $n$-vertex graph $G$ is $(c,t)$-sparse for some $t$, and has at least $C t^{1-1/\ell}n^{1+1/\ell}$ edges, then $G$ contains an induced copy of $C_{2\ell}$. This resolves a conjecture of Fox, Nenadov and Pham.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2026 1verdicts
ACCEPT 1roles
background 1polarities
support 1representative citing papers
citing papers explorer
-
Supersaturation of induced even cycles in locally sparse graphs
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.