Supersaturation of induced even cycles in locally sparse graphs
A graph $Γ$ is $(c,t)$-sparse for $c > 0$ and $t \ge 1$ if for every pair of vertex subsets $A, B \subseteq V(Γ)$ 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 $Γ$ is $(1-\varepsilon,t)$-sparse for some $t$, and has at least $Ct^{1-1/\ell}n^{1+1/\ell}$ edges, then $Γ$ 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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.04985
curl -X POST /api/v1/records/arxiv/2608.04985/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.04985/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'