Supersaturation of induced even cycles in locally sparse graphs

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 \ge 2$, there are $\epsilon >0,C,C^{\prime }>0$ such that if an $n$-vertex graph $\Gamma$ is $(1-\epsilon ,t)$-sparse for some $t$, and has at least $C{t}^{1-1/\ell }{n}^{1+1/\ell }$ edges, then $\Gamma$ contains at least $C^{\prime }{n}^2{t}^{2\ell -2}$ induced copies of $C_{2\ell }$. This partially resolves a problem of Ding, Gao, Liu, Luan, and Sun.

10 pages, comments are welcome