Mutually orthogonal cycle systems

Abstract

An ℓ-cycle system ℱ of a graph Γ is a set of ℓ-cycles which partition the edge set of Γ. Two such cycle systems ℱ and ℱ′ are said to be orthogonal if no two distinct cycles from ℱ ∪ ℱ′ 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 ℓ-cycle systems of Γ is said to be a set of mutually orthogonal cycle systems of Γ.

Let μ(ℓ,n) (respectively, μ′(ℓ,n)) be the maximum integer μ such that there exists a set of μ mutually orthogonal (cyclic) ℓ-cycle systems of the complete graph K_n. We show that if ℓ ≥ 4 is even and n ≡ 1 (mod  2ℓ), then μ′(ℓ,n), and hence μ(ℓ,n), is bounded below by a constant multiple of n/ℓ². In contrast, we obtain the following upper bounds: μ(ℓ,n) ≤ n − 2; μ(ℓ,n) ≤ (n−2)(n−3)/(2(ℓ−3)) when ℓ ≥ 4; μ(ℓ,n) ≤ 1 when ℓ > n/√2; and μ′(ℓ,n) ≤ n − 3 when n ≥ 4. We also obtain computational results for small values of n and ℓ.