Mutually orthogonal cycle systems

Andrea C. Burgess; Nicholas J. Cavenagh; David A. Pike

Ars mathematica contemporanea, Volume 23 (2023) no. 2, article no. 05, 20 p.

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 Kn. 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/ℓ2. 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 ℓ.

Article information

DOI: 10.26493/1855-3974.2692.86d

Keywords: Orthogonal cycle decompositions, cyclic cycle systems, Heffter arrays, completely-reducible, super-simple