The extremal function for cycles of length \(\ell\) mod \(k\) (Q510312)

Summary: S. A. Burr and P. Erdős conjectured that for each \(k,\ell \in \mathbb Z^+\) such that \(k \mathbb Z + \ell\) contains even integers, there exists \(c_k(\ell)\) such that any graph of average degree at least \(c_k(\ell)\) contains a cycle of length \(\ell\) mod \(k\). This conjecture was proved by \textit{B. Bollobás} [Bull. Lond. Math. Soc. 9, 97--98 (1977; Zbl 0348.05104)], and many successive improvements of upper bounds on \(c_k(\ell)\) appear in the literature. In this short note, for \(1 \leq \ell \leq k\), we show that \(c_k(\ell)\) is proportional to the largest average degree of a \(C_{\ell}\)-free graph on \(k\) vertices, which determines \(c_k(\ell)\) up to an absolute constant. In particular, using known results on Turán numbers for even cycles, we obtain \(c_k(\ell) = O(\ell k^{2/\ell})\) for all even \(\ell\), which is tight for \(\ell \in \{4,6,10\}\). Since the complete bipartite graph \(K_{\ell - 1,n - \ell + 1}\) has no cycle of length \(2\ell\) mod \(k\), it also shows \(c_k(\ell) = \Theta(\ell)\) for \(\ell = \Omega(\log k)\).