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

Benny Sudakov¹ ; Jacques Verstraete²

¹Department of Mathematics ETH Zurich Ramistrasse 101 8092 Zurich, Switzerland
²Department of Mathematics University of California at San Diego 9500 Gilman Drive, La Jolla California 92093-0112, USA.

The electronic journal of combinatorics, Tome 24 (2017) no. 1

Résumé

Burr and 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 Bollobás, 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)$.

Détail

DOI : 10.37236/6257

Classification : 05C38, 05C12, 05C15, 05C35
Mots-clés : cycle lengths, Turán numbers, chromatic number