Mutually orthogonal cycle systems

An ${\ell}$-cycle system ${\mathcal F}$ of a graph $Γ$ is a set of ${\ell}$-cycles which partition the edge set of $Γ$. Two such cycle systems ${\mathcal F}$ and ${\mathcal F}'$ are said to be {\em orthogonal} if no two distinct cycles from ${\mathcal F}\cup {\mathcal F}'$ 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 $Γ$ is said to be a set of mutually orthogonal cycle systems of $Γ$. Let $μ(\ell,n)$ (respectively, $μ'(\ell,n)$) be the maximum integer $μ$ such that there exists a set of $μ$ mutually orthogonal (cyclic) $\ell$-cycle systems of the complete graph $K_n$. We show that if $\ell\geq 4$ is even and $n\equiv 1\pmod{2\ell}$, then $μ'(\ell,n)$, and hence $μ(\ell,n)$, is bounded below by a constant multiple of $n/\ell^2$. In contrast, we obtain the following upper bounds: $μ(\ell,n)\leq n-2$; $μ(\ell,n)\leq (n-2)(n-3)/(2(\ell-3))$ when $\ell \geq 4$; $μ(\ell,n)\leq 1$ when $\ell>n/\sqrt{2}$; and $μ'(\ell,n)\leq n-3$ when $n \geq 4$. We also obtain computational results for small values of $n$ and $\ell$.

No reviews yet.

No comments yet.