Mutually orthogonal cycle systems

Abstract

An $\ell$-cycle system $\mathcal{F}$ of a graph $\Gamma$ is a set of $\ell$-cycles which partition the edge set of $\Gamma$. Two such cycle systems $\mathcal{F}$ and ${\mathcal{F}}^{\prime }$ are said to be {\em orthogonal} if no two distinct cycles from $\mathcal{F}\cup {\mathcal{F}}^{\prime }$ share more than one edge. Orthogonal cycle systems naturally arise from face $2$-colourable polyehdra and in higher genus from Heffter arrays with certain orderings. A set of pairwise orthogonal $\ell$-cycle systems of $\Gamma$ is said to be a set of mutually orthogonal cycle systems of $\Gamma$. Let $\mu (\ell ,n)$ (respectively, ${\mu }^{\prime }(\ell ,n)$) be the maximum integer $\mu$ such that there exists a set of $\mu$ mutually orthogonal (cyclic) $\ell$-cycle systems of the complete graph $K_n$. We show that if $\ell \ge 4$ is even and $n\equiv 1(\mathrm{mod}2\ell )$, then ${\mu }^{\prime }(\ell ,n)$, and hence $\mu (\ell ,n)$, is bounded below by a constant multiple of $n/{\ell }^2$. In contrast, we obtain the following upper bounds: $\mu (\ell ,n)\le n-2$; $\mu (\ell ,n)\le (n-2)(n-3)/(2(\ell -3))$ when $\ell \ge 4$; $\mu (\ell ,n)\le 1$ when $\ell >n/\sqrt{2}$; and ${\mu }^{\prime }(\ell ,n)\le n-3$ when $n\ge 4$. We also obtain computational results for small values of $n$ and $\ell$.