Induced Turán number for C_{2ℓ} in sparse graphs

Conjecture 6.1 · arXiv:2405.05902

arXiv Conjecture high confidence— first stated 2024-06-08

Authors: Jacob Fox, Rajko Nenadov, Huy Tuan Pham

Status solved high confidence

Conjecture 6.1 from arXiv:2405.05902, asserting that ex(Gamma, P_{C_{2l}}) <= C t^{1-1/l} n^{1+1/l} for every (c,t)-sparse graph Gamma, was resolved by Ding, Gao, Liu, Luan, and Sun in November 2024. Their paper arXiv:2411.12659 proves that if an n-vertex (c,t)-sparse graph has at least C t^{1-1/l} n^{1+1/l} edges then it must contain an induced copy of C_{2l}, establishing the conjectured bound.

Cited literature (1)

proof Induced even cycles in locally sparse graphs (2024)

Laihao Ding, Jun Gao, Hong Liu, Bingyu Luan, Shumin Sun · arXiv preprint · arXiv:2411.12659

Proves that every (c,t)-sparse n-vertex graph with at least C t^{1-1/l} n^{1+1/l} edges contains an induced copy of C_{2l}, thereby resolving the conjecture of Fox, Nenadov, and Pham.

Reviewer notes. arXiv:2411.12659 (submitted 2024-11-19) explicitly states in its abstract that it resolves the conjecture of Fox, Nenadov and Pham, with the bound matching Conjecture 6.1 exactly.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every $c>0$ and integer $\ell$ there exists $C>1$, such that if $\Gamma$ is a $(c,t)$-sparse graph then $\mathrm{ex}(\Gamma,\mathcal{P}_{C_{2\ell}})\leq Ct^{1-1/\ell}n^{1+1/\ell}$.

Context

The conjecture concerns the induced Turán number for even cycles $C_{2\ell}$ in $(c,t)$-sparse graphs. It is motivated by the fact that the family $\mathcal{F}_{C_{2\ell}}$ of clique quotients consists of all cycles of length between $\ell$ and $2\ell$, and that graphs of girth larger than $2\ell$ on $n$ vertices have at most $O(n^{1+1/\ell})$ edges.

Also stated in

The largest subgraph without a forbidden induced subgraph (2024-06-08)

Source paper

The largest subgraph without a forbidden induced subgraph
Jacob Fox, Rajko Nenadov, Huy Tuan Pham · 2024-06-08
https://arxiv.org/abs/2405.05902