Even cycle decomposition thresholds for dense multipartite graphs

Abstract

Let $r\ge 2$ be an integer. An $r$-partite graph $\Gamma$ with vertex partition $V_1,\dots ,V_r$ is $2$-balanced if there exists a positive integer $n$ such that $n\le |V_i|\le 2n$ for every $i\in [r]$. For an integer $\ell \ge 3$, let $C_{\ell }$ denote the cycle of length $\ell$, and define $\hat{\delta }(\Gamma )=\min \{d_{\Gamma }(v,V_i)/|V_i|:i\in [r],v\in V(\Gamma )\setminus V_i\}$. Let ${\hat{\delta }}_{C_{\ell }}^r$ denote the $C_{\ell }$-decomposition threshold for $2$-balanced $r$-partite graphs, that is, the least nonnegative real number $\delta$ such that, for every $\epsilon >0$, there exists $n_0$ such that every $C_{\ell }$-divisible $2$-balanced $r$-partite graph $G$ with ${\min }_i|V_i|>n_0$ and $\hat{\delta }(G)\ge \delta +\epsilon$ admits a $C_{\ell }$-decomposition. We prove that ${\hat{\delta }}_{C_4}^r=\frac{2}{3}$ and ${\hat{\delta }}_{C_{2k}}^r=\frac{1}{2}$ for every $r\ge 2$ and every $k\ge 3$.