ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P2.05 https://doi.org/10.26493/1855-3974.2692.86d (Also available at http://amc-journal.eu) Mutually orthogonal cycle systems* Andrea C. Burgess † Department of Mathematics and Statistics, University of New Brunswick, Saint John, NB, E2L 4L5, Canada Nicholas J. Cavenagh Department of Mathematics, The University of Waikato, Private Bag 3105, Hamilton 3240, New Zealand David A. Pike Department of Mathematics and Statistics, Memorial University of Newfoundland, St. John’s, NL, A1C 5S7, Canada Received 8 September 2021, accepted 23 June 2022, published online 17 November 2022 Abstract An ℓ-cycle system F of a graph Γ is a set of ℓ-cycles which partition the edge set of Γ. Two such cycle systems F and F ′ are said to be orthogonal if no two distinct cycles from F ∪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 ℓ-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 ℓ. Keywords: Orthogonal cycle decompositions, cyclic cycle systems, Heffter arrays, completely-redu- cible, super-simple. Math. Subj. Class. (2020): 05B30 *Authors A.C. Burgess and D.A. Pike acknowledge research support from NSERC Discovery Grants RGPIN- 2019-04328 and RGPIN-2016-04456, respectively. Thanks are given to the Centre for Health Informatics and Analytics of the Faculty of Medicine at Memorial University of Newfoundland for access to computational re- sources. †Corresponding author. cb This work is licensed under https://creativecommons.org/licenses/by/4.0/ 2 Ars Math. Contemp. 23 (2023) #P2.05 1 Introduction We say that a graph Γ decomposes into subgraphs Γ1,Γ2, . . . ,Γt, if the edge sets of the Γi partition the edges of Γ. If F = {Γi | 1 ≤ i ≤ t} where Γi ∼= H for each 1 ≤ i ≤ t, then we say that F is an H-decomposition of Γ. An ℓ-cycle system of a graph Γ is a decomposition of Γ into ℓ-cycles. In the case where Γ is the complete graph Kn we say that there is an ℓ-cycle system of order n. Necessary and sufficient conditions for the existence of an ℓ-cycle system of order n were given in [1, 26]; see also [6]. Namely, at least one ℓ-cycle system of order n > 1 exists if and only if 3 ≤ ℓ ≤ n, n(n − 1) ≡ 0 (mod 2ℓ) and n is odd. Two ℓ-cycle systems F and F ′ of the same graph Γ are said to be orthogonal if, for all cycles C ∈ F and C ′ ∈ F ′, C and C ′ share at most one edge. A set of pairwise orthogonal ℓ-cycle systems of Γ is said to be a set of mutually orthogonal cycle systems of Γ. In this paper we are interested in the maximum µ such that there exists a set of µ mutually orthogonal ℓ-cycle systems of order n; we denote this value by µ(ℓ, n). In the array below we exhibit a set of four mutually orthogonal cycle systems of order 9. We have determined computationally that µ(4, 9) = 4; i.e., this set is maximum. {(1, 2, 3, 4), (1, 3, 6, 5), (1, 6, 2, 7), (1, 8, 2, 9), (2, 4, 7, 5), (3, 5, 8, 7), (3, 8, 6, 9), (4, 5, 9, 8), (4, 6, 7, 9)}, {(1, 2, 6, 8), (1, 3, 5, 7), (1, 4, 8, 5), (1, 6, 5, 9), (2, 3, 6, 4), (2, 5, 4, 9), (2, 7, 3, 8), (3, 4, 7, 9), (6, 7, 8, 9)}, {(1, 2, 8, 7), (1, 3, 4, 6), (1, 4, 9, 8), (1, 5, 3, 9), (2, 3, 8, 5), (2, 4, 5, 6), (2, 7, 5, 9), (3, 6, 9, 7), (4, 7, 6, 8)}, {(1, 2, 9, 3), (1, 4, 6, 9), (1, 5, 4, 7), (1, 6, 3, 8), (2, 3, 7, 6), (2, 4, 8, 7), (2, 5, 6, 8), (3, 4, 9, 5), (5, 7, 9, 8)}. Orthogonal cycle systems arise from face 2-colourable embeddings of graphs on sur- faces, which satisfy two conditions natural to polyhedra and similar phenomena: each pair of faces share at most one edge and each edge belongs to exactly two faces. Let µKn be the multigraph in which each edge of Kn is replaced by µ parallel edges. A decomposition F of µKn into a subgraph H is said to be super-simple if no two copies of H share more than one edge, and completely-reducible if F partitions into µ decompositions of Kn. It follows that a set of µ mutually orthogonal cycle systems of Kn is equivalent to a completely-reducible super-simple decomposition of µKn into cycles; see [12] for more details. In the case ℓ = 3, observe that a pair of ℓ-cycle systems is orthogonal if and only if the cycle systems are disjoint. It is not hard to see that there are at most n − 2 pairwise disjoint triple systems of order n; a set of systems which meets this bound is called a large set of disjoint Steiner triple systems, or LTS(n). An LTS(7) does not exist [13]; however E-mail addresses: andrea.burgess@unb.ca (Andrea C. Burgess), nickc@waikato.ac.nz (Nicholas J. Cavenagh), dapike@mun.ca (David A. Pike) A. C. Burgess et al.: Mutually orthogonal cycle systems 3 in [23, 24], it is shown that an LTS(n) exists if and only if n > 7 and n ≡ 1 or 3 (mod 6), except for a finite list of possible exceptions. The exceptional cases are all solved in [27]. In this paper, we are often interested in cyclic cycle systems of the complete graph Kn. Let G be an additive group of order n and suppose Kn has vertex set G. Given a cycle C = (c0, c1, . . . , cℓ−1) in Kn, for each element g ∈ G, define the cycle C + g = (c0+ g, c1+ g, . . . , cℓ−1+ g). We say that a cycle system F of Kn is G-regular if, for any C ∈ F and g ∈ G, we have that C + g ∈ F . In the case that G is a cyclic group, we refer to a Zn-regular cycle system as cyclic. In a cyclic cycle system F , the orbit of the cycle C ∈ F is the set of cycles {C + g | g ∈ Zn}; a cyclic cycle system can be completely specified by listing a set of starter cycles, that is, a set of representatives for the orbits of the cycles under the action of Zn. The existence problem for cyclic cycle systems has attracted much attention. Clearly, in order for a cyclic ℓ-cycle system of odd order n to exist, we must have that 3 ≤ ℓ ≤ n and ℓ divides n(n−1)/2. However, additional conditions for existence also come into play. There is no cyclic ℓ-cycle system of order n when (ℓ, n) ∈ {(3, 9), (15, 15)}; ℓ = n = pm for some prime p and integer m ≥ 2; or ℓ < n < 2ℓ and gcd(ℓ, n) is a prime power [7, 9]. Buratti [7] has conjectured that a cyclic ℓ-cycle system of order n exists for any other admissible pair (ℓ, n); this conjecture is still open. The existence problem for cyclic cycle systems of the complete graph has been solved in a number of cases, including when n ≡ 1 or ℓ (mod 2ℓ) [8, 9, 22, 25, 28] (see also [4, 5, 18]), ℓ ≤ 32 [31, 32], ℓ is twice or thrice a prime power [30, 31, 32], or ℓ is even and m > 2ℓ [29]. We explore the maximum µ′ such that there exists a set of µ′ mutually orthogonal cyclic ℓ-cycle systems of order n; this value is denoted by µ′(ℓ, n). Pairs of orthogonal cyclic cycle systems of the complete graph arise from Heffter arrays with certain orderings. A Heffter array H(n; k) is an n × n matrix such that each row and column contains k filled cells, each row and column sum is divisible by 2nk + 1 and either x or −x appears in the array for each integer 1 ≤ x ≤ nk. A Heffter array is said to have a simple ordering if, for each row and column, the entries may be cyclically ordered so that all partial sums are distinct modulo 2nk + 1. The following was first shown by Archdeacon [2] as part of a more general result; consult [11] to see this result stated more explicitly. Theorem 1.1. If H(n; k) is a Heffter array with a simple ordering, then there exists a pair of orthogonal cyclic decompositions of K2nk+1 into k-cycles. In particular, µ′(k, 2nk + 1) ≥ 2. Thus the following is implied by existing literature on Heffter arrays. Theorem 1.2 ([3, 11, 14, 17]). Let n ≥ k. Then µ′(k, 2nk + 1) ≥ 2 whenever: • k ∈ {3, 5, 7, 9} and nk ≡ 3 (mod 4); • k ≡ 0 (mod 4); • n ≡ 1 (mod 4) and k ≡ 3 (mod 4); • n ≡ 0 (mod 4) and k ≡ 3 (mod 4) (for large enough n). With an extra condition on the orderings of the entries of a Heffter array, these orthogo- nal cycle systems in turn biembed to yield a face 2-colourable embedding on an orientable surface. Face 2-colourable embeddings on orientable surfaces have been studied for a va- riety of combinatorial structures [16, 19, 20, 21]. Recently, Costa, Morini, Pasotti and 4 Ars Math. Contemp. 23 (2023) #P2.05 Pellegrini [15] employed a generalization of Heffter arrays to construct pairs of orthogonal ℓ-cycle systems of the complete multipartite graph in certain cases. In [12], it is shown that for every graph H and fixed integer k ≥ 1, for sufficiently large n (satisfying some elementary necessary divisibility conditions), there exists a set of k pairwise orthogonal decompositions of Kn into H (i.e., no two copies of H share more than one edge). Aside from this quite general asymptotic result, to our knowledge, sets of mutually orthogonal ℓ-cycle systems of size greater than 2 have not been studied for ℓ ≥ 4. In this paper, our focus for cyclic cycle systems is in the case n ≡ 1 (mod 2ℓ), for which it is possible to construct a cyclic ℓ-cycle system with no short orbit. In particular, we will find lower bounds on µ(ℓ, n) by constructing sets of mutually orthogonal cyclic even cycle systems. Specifically, we show that if ℓ is even and n ≡ 1 (mod 2ℓ), then µ′(ℓ, n) is bounded below by a constant multiple of n/ℓ2, i.e., µ′(ℓ, n) = Ω(n/ℓ2). Our main result is as follows. Theorem 1.3. If ℓ ≥ 4 is even, n ≡ 1 (mod 2ℓ) and N = (n− 1)/(2ℓ), then µ(ℓ, n) ≥ µ′(ℓ, n) ≥ N aℓ+ b − 1, where (a, b) = { (4,−2), if ℓ ≡ 0 (mod 4), (24,−18), if ℓ ≡ 2 (mod 4). In Section 2, when ℓ = 4, we improve the bound of Theorem 1.3 to µ(ℓ, n) ≥ µ′(ℓ, n) ≥ 4N (Lemma 2.1). Section 3 establishes some notation and preliminary results. The general result for ℓ ≡ 0 (mod 4) is proved in Section 4 (Theorem 4.3), while the bound for ℓ ≡ 2 (mod 4) is proved in Section 5 (Theorem 5.5). In contrast, in Section 6 we establish upper bounds, namely µ(ℓ, n) ≤ n− 2; µ(ℓ, n) ≤ (n− 2)(n− 3)/(2(ℓ− 3)) for ℓ ≥ 4; µ(ℓ, n) ≤ 1 for ℓ > √ n(n− 1)/2; and µ′(ℓ, n) ≤ n − 3 for n ≥ 4. Finally, computational results for small values are given in the appendix. 2 Mutually orthogonal 4-cycle systems Clearly n ≡ 1 (mod 8) is a necessary condition for a decomposition of Kn into 4-cycles, cyclic or otherwise. Let [a, b, c, d]n denote the Zn-orbit of the 4-cycle (0, a, a+b, a+b+c), where a+b+c+d is divisible by n. Observe that [a, b, c, d]n = [−d,−c,−b,−a]n. Where the context is clear, we write [a, b, c, d]n = [a, b, c, d]. Let Dn = {1, 2, . . . , (n − 1)/2}; that is, Dn is the set of differences in Zn. We consider Zn as the set ±Dn ∪ {0}. By observation, the maximum size of a set of mutually orthogonal cyclic 4-cycle sys- tems of K9 is µ′(4, 9) = 2. Two such systems are [1,−2, 4,−3]9 and [1,−3, 4,−2]9. In the non-cyclic case, an exhaustive computational search indicates that the maximum size of a set of mutually orthogonal 4-cycle systems of K9 is µ(4, 9) = 4; see the example given in Section 1. Lemma 2.1. If n ≡ 1 (mod 8) and n ≥ 17, then there exists a set of (n − 1)/2 mutually orthogonal cyclic 4-cycle systems of order n. In particular, µ′(4, n) ≥ (n− 1)/2. Proof. We first describe how to construct a set of (n − 5)/2 mutually orthogonal cyclic 4-cycle systems; then we add two more by making some adjustments. A. C. Burgess et al.: Mutually orthogonal cycle systems 5 Let N = (n − 1)/8. For each i, j with 1 ≤ i < j ≤ 2N , let Ci,j and C ′i,j be the pair of orbits of 4-cycles: Ci,j := {[2i− 1, 2j,−2i,−(2j − 1)]}, C ′i,j := {[2i− 1,−(2j − 1),−2i, 2j]}. Next, let F1, F2, . . . F2N−1 be a set of 1-factors which decompose the complete graph on vertex set {1, 2, . . . , 2N}. For each 1-factor Fk, the sets Fk := ⋃ {i,j}∈Fk i 0 and suppose there exist integers d and d′ such that d, d′ ∈ (N/2 − δN,N/2 + δN). If α and α′ are integers such that 1 ≤ α < α′ ≤ (1 − 2δ)/4δ, then αd < α′d′. Proof. Note that if δ > 110 , then the result is vacuously true since (1− 2δ)/4δ < 2. So we assume δ ≤ 110 . For each positive integer s, define Is = {si | N/2− δN < i < N/2 + δN ; i ∈ R}. Let m = ⌊ 1−2δ4δ ⌋, and let S = [1,m]. Observe that α, α ′ ∈ S. Now, δ ≤ 1/(4m + 2) implies that: m(1 + 2δ) ≤ (m+ 1)(1− 2δ) ⇒ m(N/2 + δN) ≤ (m+ 1)(N/2− δN). It follows that for each s ∈ S, every element of Is is strictly less than every element of Is+1. Since αd ∈ Iα and α′d′ ∈ Iα′ , it follows that αd < α′d′. The following variation of Lemma 3.5 will be used in Section 5. Corollary 3.6. Let δ,N > 0 and suppose there exist integers d and d′ such that d, d′ ∈ (N/3 − δN,N/3 + δN). If α and α′ are integers such that 1 ≤ α < α′ ≤ (1 − 3δ)/6δ, then αd < α′d′. Proof. If m is a positive integer, m ≤ (1− 3δ)/6δ implies that m(N/3 + δN) ≤ (m+ 1)(N/3− δN). The remaining argument is similar to the previous lemma. 8 Ars Math. Contemp. 23 (2023) #P2.05 4 Orthogonal sets of 4k-cycle systems with k ≥ 2 Our aim in this section is to prove Theorem 4.3. In particular, for each k ≥ 2 and n ≡ 1 (mod 8k), we will show that µ′(n, 4k) = Ω(n/k2). That is, we construct a set of mutually orthogonal 4k-cycle decompositions of Kn of size at least cn/k2 where c is a constant. In particular, the number of mutually orthogonal decompositions constructed is⌈ n− 1 8k(16k − 2) − 1 ⌉ ; thus we have at least two orthogonal decompositions whenever n− 1 8k(16k − 2) > 2, or equivalently n− 1 > 32k(8k − 1). Let N and k be positive integers and let n = 8kN + 1. For each integer d ∈ (N/2 − N/(16k−2), N/2) (there is at least one such integer whenever N > 16k−2), we construct a cyclic 4k-cycle decomposition of Kn which we will denote by F(d). The first d starter cycles in F(d) use the set of differences [1, 4kd]. For i ∈ [1, d], let Sd,i = {i, d+ i, 2d+ i, . . . , (4k − 1)d+ i}. Observe that the set Sd,i is balanced, with τ = k, for each i ∈ [1, d]. Henceforth in this section, let e := N − d. (In effect, e is a function of d.) Observe that e ∈ (N/2, N/2 + N/(16k − 2)). The remaining e starter cycles in F(d) use differences [4kd+ 1, 4kN ]. For i ∈ [1, e], take Te,i = {4kd+ i, 4kd+ e+ i, 4kd+ 2e+ i, . . . , 4kd+ (4k − 1)e+ i}. Observe that the set Te,i is balanced for each i ∈ [1, e], where τ = k. Moreover, since 4kd+ 4ke = 4kN , we have that( d⋃ i=1 Sd,i ) ∪ ( e⋃ i=1 Te,i ) = [1, 4kN ], so by Corollary 3.4, the set of cycles F(d) := {C(Sd,i) | i ∈ [1, d]} ∪ {C(Te,i) | i ∈ [1, e]} is a set of starter cycles for a cyclic 4k-cycle system of order n = 8kN + 1. In order to show that we have constructed an orthogonal set of decompositions, we will make use of the following, which is a direct consequence of Lemma 3.5. Lemma 4.1. Suppose d, d′ ∈ (N/2 − N/(16k − 2), N/2) such that d ̸= d′, and let e = N − d and e′ = N − d′. Let α, α′ ∈ [1, 4k− 1]. Then no two of αd, α′d′, αe and α′e′ are equal. Moreover, if α < α′ then αd < α′d′ and αe < α′e′. Lemma 4.2. Suppose d, d′ ∈ (N/2 − N/(16k − 2), N/2) such that d ̸= d′. Then the decompositions F(d) and F(d′), as defined above, are orthogonal. A. C. Burgess et al.: Mutually orthogonal cycle systems 9 Proof. In what follows, d ̸= d′, e = N − d and e′ = N − d′. Observe that e, e′ ∈ (N/2, N/2 +N/(16k − 2)). It suffices to show that if C is a cycle from F(d) and C ′ is a cycle from F(d′), then C and C ′ share at most one difference. Equivalently, we will show that: (i) For any i ∈ [1, d] and i′ ∈ [1, d′], |Sd,i ∩ Sd′,i′ | ≤ 1; (ii) For any i ∈ [1, e] and i′ ∈ [1, e′], |Te,i ∩ Te′,i′ | ≤ 1; and (iii) For any i ∈ [1, d] and i′ ∈ [1, e′], |Sd,i ∩ Te′,i′ | ≤ 1. To show (i), suppose to the contrary that {x, y} ⊆ Sd,i ∩ Sd′,i′ with x < y. Thus y−x = αd = α′d′ for some α, α′ ∈ [1, 4k−1], contradicting Lemma 4.1. The justification of (ii) is similar. For (iii), if x, y ∈ Sd,i ∩ Te′,i′ with x < y, then y − x = αd for some α ∈ [1, 4k − 1] (since x, y ∈ Sd,i) and y − x = α′e′ for some α′ ∈ [1, 4k − 1] (since x, y ∈ Te′,i′ ), so αd = α′e′, which again contradicts Lemma 4.1. We note that the existence of two distinct integers in (N/2 − N/(16k − 2), N/2) is guaranteed when N > 4(8k − 1), i.e. n− 1 > 32k(8k − 1). Since n = 8Nk + 1, we have the following theorem. Theorem 4.3. Let k ≥ 2 and n = 8Nk + 1. There is a set of mutually orthogonal cyclic 4k-cycle systems of order n of size at least N 16k − 2 − 1 = n− 1 8k(16k − 2) − 1. Thus, if n ≡ 1 (mod 8k), µ(n, 4k) ≥ µ′(n, 4k) ≥ n− 1 8k(16k − 2) − 1. 5 Orthogonal sets of (4k + 2)-cycles In this section, we show that for positive integers k and n ≡ 1 (mod 8k+4), µ′(n, 4k+2) = Ω(n/k2). Specifically, we construct⌈ n− 1 (8k + 4)(96k + 30) − 1 ⌉ mutually orthogonal cyclic (4k + 2)-cycle decompositions of Kn. Thus we have at least two orthogonal decompositions whenever n− 1 (8k + 4)(96k + 30) > 2, or equivalently n− 1 > 48(2k + 1)(16k + 5). 10 Ars Math. Contemp. 23 (2023) #P2.05 Let N and k be positive integers and let n = 2(4k+2)N+1. For each d ≡ N (mod 2) with d ∈ (N/3 − N/(48k + 15), N/3) (there is at least one such integer whenever N > 48k+15), we form a cyclic (4k+2)-cycle decomposition F(d) of Kn. Let e = (N−d)/2, and observe that N/3 < e < N/3 + N/(2(48k + 15)) < N/3 + N/(48k + 15). Thus e ∈ (N/3, N/3 +N/(48k + 15)). For i ∈ [1, d], let Sd,i,1 = {i, d+i, 2d+i, . . . , (4k−1)d+i} and Sd,i,2 = {4kN+4e+i, (4k+2)N−i+1}, and let Sd,i = Sd,i,1 ∪ Sd,i,2. Now, when constructing the cycles containing differences in Sd,i, instead of (4k + 2)N − i + 1, we will use the negative of this difference modulo n, that is, the value (8k + 4)N + 1− ((4k + 2)N − i+ 1) = (4k + 2)N + i. We construct a starter cycle C ′(Sd,i) using the set of differences Sd,i but in a slightly different way to Lemma 3.3. C ′(Sd,i) =(0,−i, d,−d− i, . . . , kd,−kd− i, (k + 2)d, − (k + 1)d− i, (k + 3)d,−(k + 2)d− i, . . . , 2kd,−(2k − 1)d− i, (4k + 2)N − (2k + 1)d,−(2k + 1)d− i). (Note that in the case k = 1, C ′(Sd,i) = (0,−i, d,−d− i, 4N + e− d,−3d− i).) Lemma 5.1. Let i ∈ [1, d]. Working modulo n, the ordered sequence C ′(Sd,i) is a (4k+2)- cycle with difference set Sd,i. Proof. To see that no vertices are repeated (modulo n) within the sequence C ′(Sd,i), it suffices to observe that: − (4k + 2)N < −(2k + 1)d− i < −(2k − 1)d− i < −(2k − 2)d− i < · · · < −d− i < −i < 0 < d < 2d < · · · < kd < (k + 2)d < (k + 3)d < · · · < 2kd < (4k + 2)N − (2k + 1)d < (4k + 2)N. By inspection, and since (4k + 2)N − (2k + 1)d = 4kN + 4e − (2k − 1)d and n− ((4k+ 2)N − i+ 1) = (4k+ 2)N + i, the set of differences of the edges of the cycle C ′(Sd,i) is Sd,i. Note that d⋃ i=1 Sd,i = [1, 4kd] ∪ [4kN + 4e+ 1, 4kN + 4e+ d] ∪ [(4k + 2)N − d+ 1, (4k + 2)N ]; since 4kN + 4e+ d = (4k + 2)N − d, we have that d⋃ i=1 Sd,i = [1, 4kd] ∪ [4kN + 4e+ 1, (4k + 2)N ]. A. C. Burgess et al.: Mutually orthogonal cycle systems 11 For j, ℓ ∈ [1, e], let Te,j,1 = {4kd+ j, 4kd+ e+ j, . . . , 4kd+ (4k − 1)e+ j}, Te,j,2 = {4kN + j, 4kN + 2e+ j}, Ue,ℓ,1 = {4kd+ 4ke+ ℓ, 4kd+ (4k + 1)e+ ℓ, . . . , 4kd+ (8k − 1)e+ ℓ}, Ue,ℓ,2 = {4kN + e+ ℓ, 4kN + 3e+ ℓ}, and set Te,j = Te,j,1 ∪ Te,j,2 and Ue,ℓ = Ue,ℓ,1 ∪ Ue,ℓ,2. The sets Te,j and Ue,ℓ are each balanced with τ = k + 1. We have that e⋃ j=1 Te,j  ∪( e⋃ ℓ=1 Ue,ℓ ) = [4kd+ 1, 4kd+ 8ke] ∪ [4kN + 1, 4kN + 4e] = [4kd+ 1, 4kN + 4e], since 4kd+ 8ke = 4kN . Observe that for fixed d,( d⋃ i=1 Sd,i ) ∪  e⋃ j=1 Te,j  ∪( e⋃ ℓ=1 Ue,ℓ ) = [1, (4k + 2)N ], and thus by Corollary 3.4 and Lemma 5.1, the set of cycles F(d) = {C ′(Sd,i) | i ∈ [1, d]} ∪ {C(Te,j) | j ∈ [1, e]} ∪ {C(Ue,ℓ) | ℓ ∈ [1, e]} is a set of starter cycles for a (4k + 2)-cycle decomposition of Kn. In order to show that the decompositions F(d), d ∈ (N/3 − N/(48k + 15), N/3), are orthogonal, we will make use of the following lemma which is directly implied by Corollary 3.6. Lemma 5.2. Suppose there exist integers d, d′, e, e′ ∈ ( N 3 − N 48k + 15 , N 3 + N 48k + 15 ) such that d ̸= d′ and e ̸= e′. Let α, α′ ∈ [1, 8k + 2]. Then αd ̸= α′d′ and αe ̸= α′e′. Moreover, if α < α′, then αd < α′d′ and αe < α′e′. Lemma 5.3. Suppose that βd + i = β′d′ + i′, where β, β′ ∈ [0, 4k − 1], i ∈ [1, d], i′ ∈ [1, d′] and d′ < d. Then either β′ = β or β′ = β + 1. Proof. From Lemma 5.2, (β + 1)d < (β + 2)d′. Now, (β − 1)d′ + i′ ≤ βd′ ≤ βd < βd+ i and βd+ i ≤ (β + 1)d < (β + 2)d′ < (β + 2)d′ + i′; hence (β − 1)d′ + i′ < βd+ i < (β + 2)d′ + i′. 12 Ars Math. Contemp. 23 (2023) #P2.05 Lemma 5.4. Let d ̸= d′ such that d, d′ ≡ N (mod 2) and d, d′ ∈ ( N 3 − N 48k + 15 , N 3 + N 48k + 15 ) . Let e = (N − d)/2 and e′ = (N − d′)/2. Let i ∈ [1, d], i′ ∈ [1, d′], j, ℓ ∈ [1, e] and j′, ℓ′ ∈ [1, e′]. Then for each X ∈ {Sd,i, Te,j , Ue,ℓ} and each Y ∈ {Sd′,i′ , Te′,j′ , Ue′,ℓ′}, |X ∩ Y | ≤ 1 with the exception Sd,i ∩ Sd′,i = {i, (4k + 2)N + i}. Proof. Recall from the start of this section that e, e′ ∈ (N/3, N/3 + N/(48k + 15)). In what follows, we frequently apply Lemma 5.2 to d, d′, e and e′. To prove the lemma, it suffices to show the following: (i) Sd,i ∩ Sd′,i = {i, (4k + 2)N − i+ 1} and if i ̸= i′ then |Sd,i ∩ Sd′,i′ | ≤ 1; (ii) |Te,j ∩ Te′,j′ | ≤ 1, |Ue,ℓ ∩ Ue′,ℓ′ | ≤ 1 and |Te,j ∩ Ue′,ℓ′ | ≤ 1; (iii) |Sd,i ∩ Te′,j′ | ≤ 1 and |Sd,i ∩ Ue′,ℓ′ | ≤ 1. Proof of (i). In this case, we may assume without loss of generality that d′ < d. We note that 4kN + 4e′ + i′ > 4kN > 4kd ≥ (4k − 1)d+ i and 4kN + 4e+ i > 4kN > 4kd′ ≥ (4k − 1)d′ + i′, so Sd,i,1 ∩ Sd′,i′,2 = Sd′,i′,1 ∩ Sd,i,2 = ∅. Now, supposing that |Sd,i,1 ∩ Sd′,i′,1| ≥ 2, it follows that for some x, (x, x + αd) = (x, x + α′d′) where α, α′ ∈ [1, 4k − 1]; thus αd = α′d′, in contradiction to Lemma 5.2. Next, supposing that |Sd,i,2 ∩ Sd′,i′,2| ≥ 2, then either (a) 4kN + 4e+ i = 4kN + 4e′ + i′ and (4k + 2)N − i+ 1 = (4k + 2)N − i′ + 1, or (b) 4kN + 4e+ i = (4k + 2)N − i′ + 1 and 4kN + 4e′ + i′ = (4k + 2)N − i+ 1. In both cases, it is straightforward to check that e = e′, a contradiction. Thus if |Sd,i∩Sd′,i′ | ≥ 2, it must be that |Sd,i,1∩Sd′,i′,1| = 1 and |Sd,i,2∩Sd′,i′,2| = 1. If i = i′ then {i, (4k + 2)N − i + 1} ⊆ Sd,i ∩ Sd′,i′ . Moreover, recalling that Sd,i,1 ∩ Sd′,i′,2 = Sd′,i′,1 ∩ Sd,i,2 = ∅, it follows that |Sd,i ∩ Sd′,i′ | = 2. Hence if i = i′, then Sd,i ∩ Sd′,i = {i, (4k + 2)N − i + 1}. We now assume that i ̸= i′. From Lemma 5.3, |Sd,i,1 ∩ Sd′,i′,1| = 1 implies that either (a) βd+ i = βd′ + i′, or (b) βd+ i = (β + 1)d′ + i′ for some β, β′ ∈ [0, 4k − 1]. Now suppose that also |Sd,i,2 ∩ Sd′,i′,2| = 1. Since i ̸= i′, we note that (4k + 2)N − i + 1 ̸= (4k + 2)N − i′ + 1. Also, it cannot be the case that 4kN + 4e+ i = (4k + 2)N − i′ + 1, since 4kN + 4e+ i = (4k + 2)N − 2d+ i ≤ (4k + 2)N − d < (4k + 2)N − d′ ≤ (4k + 2)N − i′ < (4k + 2)N − i′ + 1. Now suppose that 4kN + 4e + i = 4kN + 4e′ + i′. Then 2d − i = 2d′ − i′. If (a) is true, then (β + 2)d = (β + 2)d′; since β + 2 > 0, we have d = d′, a contradiction. A. C. Burgess et al.: Mutually orthogonal cycle systems 13 On the other hand, if (b) is true, then (β + 2)d = (β + 3)d′, contradicting Lemma 5.2. Thus the only remaining possibility is that 4kN + 4e′ + i′ = (4k + 2)N − i + 1, so that i+ i′ = 2N−4e′+1 = 2d′+1 is odd. Since d and d′ have the same parity, this contradicts (a), so it must be that (b) is true. It follows that (β + 3)d′ − βd+ 1 = 2i ≤ 2d. Thus (β + 3)d′ ≤ (β + 2)d− 1 < (β + 2)d, contradicting Lemma 5.2. Proof of (ii). We first note that the largest element in Te,j,1∪Ue,ℓ,1 is 4kd+(8k−1)e+ ℓ, while the smallest element of Te,j,2 ∪ Ue,ℓ,2 is 4kN + j. Since 4kd+ (8k − 1)e+ ℓ ≤ 4kd+ 8ke = 4kN < 4kN + j, it follows that Te,j,1 ∩ Te′,j′,2 = ∅, Ue,ℓ,1 ∩ Ue′,ℓ′,2 = ∅ and Te,j,1 ∩ Ue′,ℓ′,2 = ∅. Now, if |Te,j,1 ∩ Te′,j′,2| ≥ 2, |Ue,ℓ,1 ∩ Ue′,ℓ′,1| ≥ 2 or |Te,j,1 ∩ Ue′,j′,1| ≥ 2, then for some x, (x, x + αe) = (x, x + α′e′), where α, α′ ∈ [1, 8k − 1]. Thus αe = α′e′, contradicting Lemma 5.2. If |Te,j,2 ∩ Te′,j′,2| ≥ 2, |Ue,ℓ,2 ∩ Ue′,ℓ′,2| ≥ 2 or |Te,ℓ,2 ∩ Ue′,ℓ′,2| ≥ 2, then it follows that e = e′, a contradiction. Thus, if |Te,j∩Te′,j′ | ≥ 2, it must be that |Te,j,1∩Te′,j′,1| = 1 and |Te,j,2∩Te′,j′,2| = 1. Since |Te,j,1∩Te′,j′,1| = 1, we have that for some α, α′ ∈ [0, 4k−1], 4kd+αe+j = 4kd′+ α′e′+j′, which implies that (8k−α)e−j = (8k−α′)e′−j′. Since |Te,j,2∩Te′,j′,2| = 1, then 4kN+βe+j = 4kN+β′e′+j′ where β, β′ ∈ {0, 2}. Hence (8k−α+β)e = (8k− α′+β′)e′, which contradicts Lemma 5.2 since (8k−α+β), (8k−α′+β′) ∈ [4k+1, 8k+2]. We conclude that |Te,j ∩ Te′,j′ | ≤ 1. In a similar way, the assumption that |Ue,ℓ,1∩Ue,ℓ′,1| = 1 and |Ue,ℓ,2∩Ue,ℓ′,2| = 1 leads to a contradiction, as does the assumption that |Te,j,1∩Ue′,ℓ′,1| = 1 and |Te,j,2∩Ue′,ℓ′,2| = 1. We conclude that |Ue,ℓ ∩ Ue′,ℓ′ | ≤ 1 and |Te,j ∩ Ue′,ℓ′ | ≤ 1. Next, suppose that |Ue,ℓ,1 ∩ Ue′,ℓ′,1| = 1 and |Ue,ℓ,2 ∩ Ue′,ℓ′,2| = 1. Since |Ue,ℓ,1 ∩ Ue′,ℓ′,1| = 1, we have that for some α, α′ ∈ [4k, 8k− 1], 4kd+αe+ ℓ = 4kd′+α′e′+ ℓ′, which implies that (8k − α)e − ℓ = (8k − α′)e′ − ℓ. Since |Ue,ℓ,2 ∩ Ue′,ℓ′,2| = 1, then 4kN + βe + ℓ = 4kN + β′e′ + ℓ′ where β, β′ ∈ {1, 3}. Hence (8k − α + β)e = (8k − α′+β′)e′, which contradicts Lemma 5.2 since (8k−α+β), (8k−α′+β′) ∈ [2, 4k+3]. Finally, suppose that |Te,j,1 ∩ Ue′,ℓ′,1| = 1 and |Te,j,2 ∩ Ue′,ℓ′,2| = 1. Since |Te,j,1 ∩ Ue′,ℓ′,1| = 1, we have that for some α ∈ [0, 4k − 1], α′ ∈ [4k, 8k − 1], 4kd + αe + j = 4kd′ + α′e′ + ℓ′, which implies that (8k − α)e − j = (8k − α′)e′ − ℓ′. Since |Te,j,2 ∩ Ue′,ℓ′,2| = 1, then 4kN + βe + j = 4kN + β′e′ + ℓ′, where β ∈ {0, 2} and β′ ∈ {1, 3}. Hence (8k−α+β)e = (8k−α′+β′)e′, which contradicts Lemma 5.2 since 4k + 1 ≤ 8k − α+ β ≤ 8k + 2 and 2 ≤ 8k − α′ + β′ ≤ 4k + 3. Proof of (iii). Note that since (4k − 1)d+ i ≤ 4kd < 4kN < 4kN + j′ < 4kN + e′ + ℓ′, then Sd,i,1 ∩ Te′,j′,2 = ∅ and Sd,i,1 ∩ Ue′,ℓ′,2 = ∅. Moreover, 4kd′ + (4k − 1)e′ + j′ ≤ 4kd′ + 4ke′ < 4kd′ + (8k − 1)e′ + ℓ′ ≤ 4kd′ + 8ke′ = 4kN < 4kN + 4e+ i, and so Sd,i,2 ∩ Te′,j′,1 = ∅ and Sd,i,2 ∩ Ue′,ℓ′,1 = ∅. 14 Ars Math. Contemp. 23 (2023) #P2.05 By Lemma 5.2, (4k − 2)d+ i ≤ (4k − 1)d < 4kd′ < 4kd′ + j′. It follows that |Sd,i,1 ∩ Te′,j′,1| ≤ 1. Also, since d < N/3 < e′, (4k − 1)d+ i ≤ 4kd < 4ke′ < 4kd′ + 4ke′ + ℓ′, and thus Sd,i,1 ∩ Ue′,ℓ′,1 = ∅. Now, using Lemma 5.2, we also have that 4kN+e′+ℓ′ ≤ 4kN+2e′ < 4kN+2e′+j′ ≤ 4kN+3e′ < 4kN+4e < 4kN+4e+ i, and so Sd,i,2 ∩ Te′,j′,2 = ∅ and |Sd,i,2 ∩ Ue′,ℓ′,2| ≤ 1. It follows that |Sd,i ∩ Te′,j′ | ≤ 1 and |Sd,i ∩ Ue′,ℓ′ | ≤ 1. End of Proof of Lemma 5.4. Theorem 5.5. Let k ≥ 1 and n = (8k + 4)N + 1. There is a set of mutually orthogonal cyclic (4k + 2)-cycle systems of order n of size at least⌈ N 96k + 30 − 1 ⌉ = ⌈ n− 1 (8k + 4)(96k + 30) − 1 ⌉ . Thus, if n ≡ 1 (mod 2(4k + 2)), then µ(n, 4k + 2) ≥ µ′(n, 4k + 2) ≥ ⌈ n− 1 (8k + 4)(96k + 30) − 1 ⌉ . Proof. The number of integers strictly between N/3 − N/(48k + 15) and N/3 with the same parity as N is at least ⌈N/(96k + 30) − 1⌉. Note that there are at least two distinct integers of the same parity as N in this interval whenever N 96k + 30 > 2, or equivalently n − 1 > 48(2k + 1)(16k + 5). It thus suffices to show that for distinct integers d and d′ with the same parity such that d, d′ ∈ ( N 3 − N 48k + 15 , N 3 ) , the decompositions F(d) and F(d′) are orthogonal. In turn, it suffices to deal with the exceptional case from Lemma 5.4. From Lemma 5.1, the edges of differences i and (4k + 2)N − i + 1 within C ′(Sd,i) are {0,−i} and {(4k+2)N−(2k+1)d,−(2k+1)d− i}, which are at distance (4k+2)N−(2k+1)d+ i. Similarly, the edges of differences i and (4k+2)N− i+1 within C ′(Sd′,i) are {0,−i} and {(4k+2)N−(2k+1)d′,−(2k+1)d′−i}, which are at distance (4k+2)N−(2k+1)d′+i. If the pairs of edges within cycles generated from the starters C ′(Sd,i) and C ′(Sd′,i) co- incide, then we must have that (2k + 1)d ≡ (2k + 1)d′ (mod n). But n and 2k + 1 are coprime, so d = d′. A. C. Burgess et al.: Mutually orthogonal cycle systems 15 6 Concluding remarks The main results of this paper have been to establish lower bounds on the number of mu- tually orthogonal cyclic ℓ-cycle systems of order n. For upper bounds on the number of systems (not necessarily cyclic in nature) we have the following lemmata. Lemma 6.1. If there exists a set of µ mutually orthogonal ℓ-cycle systems of order n, then µ ≤ n− 2. That is, µ(ℓ, n) ≤ n− 2. Proof. Consider a vertex w in Kn. The vertex w belongs to precisely (n − 1)(n − 2)/2 paths of length 2 in Kn where w is the center vertex of the path. Moreover, each such path belongs to at most one ℓ-cycle from any set of µ mutually orthogonal ℓ-cycle systems. The number of cycles in one ℓ-cycle system which contain vertex w is equal to (n−1)/2. Thus µ(n− 1)/2 ≤ (n− 1)(n− 2)/2. The result follows. Lemma 6.2. Let ℓ ≥ 4. Then µ(ℓ, n) ≤ (n− 2)(n− 3) 2(ℓ− 3) . Proof. Suppose there exists a set {F1,F2, . . . ,Fµ} of mutually orthogonal ℓ-cycle systems of Kn. Consider an edge {v, w} in Kn. Then for each i ∈ [1, µ], there is an ℓ-cycle Ci ∈ Fi containing the edge {v, w}. Let H be the clique of size n− 2 in Kn not including vertices v and w. Then the intersection of Ci with H is a path Pi with ℓ − 3 edges. Moreover, orthogonality implies that the paths in the set {Pi | i ∈ [1, µ]} are pairwise edge-disjoint. Thus, (ℓ− 3)µ is bounded by the number of edges in H; that is, (ℓ− 3)µ ≤ (n− 2)(n− 3)/2. Observe that Lemma 6.2 improves Lemma 6.1 only if ℓ > (n+ 3)/2. If ℓ > n/ √ 2, it is not even possible to find a pair of orthogonal cycle systems, as shown in the following lemma. Lemma 6.3. If 2ℓ2 > n(n− 1) then µ(ℓ, n) ≤ 1. Proof. Suppose there exists a pair {F1,F2} of mutually orthogonal ℓ-cycle systems of Kn. Then F1 and F2 each contain n(n − 1)/(2ℓ) cycles of length ℓ. Let C be a cycle in F1. By the definition of orthogonality, each edge of C intersects a unique cycle in F2. Thus ℓ ≤ n(n− 1)/(2ℓ), contradiction. When the systems are required to be cyclic, Lemma 6.1 can be slightly improved. Lemma 6.4. Let n ≥ 4. If there exists a set of µ′ mutually orthogonal cyclic ℓ-cycle systems of order n, then µ′ ≤ n− 3. That is, µ′(ℓ, n) ≤ n− 3. Proof. Since µ′(ℓ, n) ≤ µ(ℓ, n), Lemma 6.1 implies that µ′(ℓ, n) ≤ n − 2. Suppose, for the sake of contradiction that µ′(ℓ, n) = n− 2. Thus there exists a set of n− 2 orthogonal cyclic decompositions of Kn where the vertices are labelled with elements of Zn. Let a ∈ [1, (n − 1)/2]. Suppose that the path (−a, 0, a) of length 2 does not occur in a cycle from one of these decompositions. Then the total number of paths of length 2 containing 0 which appear in one of the cycles is less than (n − 1)(n − 2)/2. However, there are (n− 2)(n− 1)/2 cycles containing vertex 0, contradicting the condition of orthogonality. 16 Ars Math. Contemp. 23 (2023) #P2.05 Let Ca be the cycle containing the path (−a, 0, a) and let F be the decomposition of Kn containing Ca. Since our decomposition is cyclic, there is also a cycle C ′ ∈ F containing (0, a, 2a); since C ′ and Ca share an edge we must have C ′ = Ca. Inductively, Ca = (0, a, 2a, . . . ). In particular C1 = (0, 1, 2, . . . , n − 1) and thus ℓ = n. But since µ′(ℓ, n) = n − 2 ≥ 2 and n > (n − 1)/2, there is a cycle C ′′ ̸= Ca in a decomposition F ′ ̸= F containing a repeated difference a ∈ [1, (n − 1)/2]. The cycle C ′′ shares two edges with Ca, contradicting the condition of orthogonality. It is worth noting that for certain congruencies the upper bound in Lemma 6.4 can be made significantly smaller. For example, if n ≡ 3 (mod 6) then µ′(3, n) = 1, because in this case any cyclic decomposition necessarily contains the cycle (0, n/3, 2n/3). In the appendix we give computational results for µ′(ℓ, n) when ℓ and n are small. As yet we are unaware of any instances for which the bound of Lemma 6.4 is tight, and so we ask if equality ever occurs. Question 1. For which values of ℓ and n, if any, is µ′(ℓ, n) = n− 3? ORCID iDs Nicholas J. Cavenagh https://orcid.org/0000-0002-9151-3842 David A. Pike https://orcid.org/0000-0001-8952-3016 References [1] B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn − I , J. Combin. Theory Ser. B 81 (2001), 77–99, doi:10.1006/jctb.2000.1996, https://doi.org/10.1006/jctb. 2000.1996. [2] D. Archdeacon, Heffter arrays and biembedding graphs on surfaces, Electron. J. Comb. 22 (2015), Paper 1.74, 14, doi:10.37236/4874, https://doi.org/10.37236/4874. [3] D. S. Archdeacon, J. H. Dinitz, D. M. Donovan and E. Ş. Yazıcı, Square integer Heffter arrays with empty cells, Des. Codes Cryptogr. 77 (2015), 409–426, doi:10.1007/s10623-015-0076-4, https://doi.org/10.1007/s10623-015-0076-4. [4] A. Blinco, S. I. El-Zanati and C. Vanden Eynden, On the cyclic decomposition of complete graphs into almost-bipartite graphs, Discrete Math. 284 (2004), 71–81, doi:10.1016/j.disc. 2003.11.024, https://doi.org/10.1016/j.disc.2003.11.024. [5] D. Bryant, H. Gavlas and A. C. H. Ling, Skolem-type difference sets for cycle systems, Elec- tron. J. Comb. 10 (2003), Research Paper 38, 12 pp., doi:10.37236/1731, https://doi. org/10.37236/1731. [6] M. Buratti, Rotational k-cycle systems of order v < 3k; another proof of the existence of odd cycle systems, J. Combin. Des. 11 (2003), 433–441, doi:10.1002/jcd.10061, https://doi. org/10.1002/jcd.10061. [7] M. Buratti, Cycle decompositions with a sharply vertex transitive automorphism group, Matem- atiche (Catania) 59 (2004), 91–105 (2006). [8] M. Buratti and A. Del Fra, Existence of cyclic k-cycle systems of the complete graph, Dis- crete Math. 261 (2003), 113–125, doi:10.1016/s0012-365x(02)00463-6, https://doi. org/10.1016/s0012-365x(02)00463-6. [9] M. Buratti and A. Del Fra, Cyclic Hamiltonian cycle systems of the complete graph, Dis- crete Math. 279 (2004), 107–119, doi:10.1016/s0012-365x(03)00267-x, https://doi. org/10.1016/s0012-365x(03)00267-x. A. C. Burgess et al.: Mutually orthogonal cycle systems 17 [10] A. Burgess, F. Merola and T. Traetta, Cyclic cycle systems of the complete multipartite graph, J. Comb. Des. 28 (2020), 224–260, doi:10.1002/jcd.21688, https://doi.org/10.1002/ jcd.21688. [11] K. Burrage, D. M. Donovan, N. J. Cavenagh and E. Ş. Yazıcı, Globally simple Heffter arrays H(n; k) when k ≡ 0, 3 (mod 4), Discrete Math. 343 (2020), 17 pp., doi:10.1016/j.disc.2019. 111787, id/No 111787, https://doi.org/10.1016/j.disc.2019.111787. [12] Y. Caro and R. Yuster, Orthogonal H-decompositions, Bull. Inst. Comb. Appl. 33 (2001), 42–48, https://www.researchgate.net/publication/268320123_ Orthogonal_H-decompositions. [13] A. Cayley, On the triadic arrangements of seven and fifteen things, London, Edinburgh and Dublin Philos. Msg. and J. Sci. 37 (1850), 50–53, doi:10.1080/14786445008646550, https: //doi.org/10.1080/14786445008646550. [14] S. Costa, F. Morini, A. Pasotti and M. A. Pellegrini, Globally simple heffter arrays and or- thogonally cyclic cycle decompositions, Australas. J. Comb. 72 (2018), 549–593, https: //ajc.maths.uq.edu.au/?page=get_volumes&volume=72. [15] S. Costa, F. Morini, A. Pasotti and M. A. Pellegrini, A generalization of Heffter arrays, J. Comb. Des. 28 (2020), 171–206, doi:10.1002/jcd.21684, https://doi.org/10.1002/ jcd.21684. [16] J. Dinitz and A. Mattern, Biembedding Steiner triple systems and n-cycle systems on orientable surfaces, Australas. J. Comb. 67 (2017), 327–344, https://ajc.maths.uq.edu.au/ ?page=get_volumes&volume=67. [17] J. H. Dinitz and I. M. Wanless, The existence of square integer Heffter arrays, Ars Math. Contemp. 13 (2017), 81–93, doi:10.26493/1855-3974.1121.fbf, https://doi.org/10. 26493/1855-3974.1121.fbf. [18] H.-L. Fu and S.-L. Wu, Cyclically decomposing the complete graph into cycles, Discrete Math. 282 (2004), 267–273, doi:10.1016/j.disc.2003.12.009, https://doi.org/10.1016/j. disc.2003.12.009. [19] M. J. Grannell and T. S. Griggs, Designs and topology, in: Surveys in combinatorics 2007, Cambridge Univ. Press, Cambridge, volume 346 of London Math. Soc. Lecture Note Ser., pp. 121–174, 2007, doi:10.1017/cbo9780511666209.006, https://doi.org/10.1017/ cbo9780511666209.006. [20] M. J. Grannell and T. A. McCourt, Doubly even orientable closed 2-cell embeddings of the complete graph, Electron. J. Comb. 21 (2014), Paper 1.22, 17 pp., doi:10.37236/3189, https: //doi.org/10.37236/3189. [21] T. S. Griggs and T. A. McCourt, Biembeddings of symmetric n-cycle systems, Graphs Comb. 32 (2016), 147–160, doi:10.1007/s00373-015-1538-1, https://doi.org/10.1007/ s00373-015-1538-1. [22] A. Kotzig, Decomposition of a complete graph into 4k-gons, Mat.-Fyz. Časopis. Sloven. Akad. Vied. 15 (1965), 229–233. [23] J. X. Lu, On large sets of disjoint Steiner triple systems. I,II, III, J. Comb. Theory Ser. A 34 (1983), 140–182, doi:10.1016/0097-3165(83)90052-3, https://doi.org/10.1016/ 0097-3165(83)90052-3. [24] J. X. Lu, On large sets of disjoint Steiner triple systems. IV, V, VI, J. Comb. Theory Ser. A 37 (1984), 136–192, doi:10.1016/0097-3165(84)90066-9, https://doi.org/10.1016/ 0097-3165(84)90066-9. [25] A. Rosa, On cyclic decompositions of the complete graph into (4m + 2)-gons, Mat.-Fyz. Časopis. Sloven. Akad. Vied. 16 (1966), 349–352. 18 Ars Math. Contemp. 23 (2023) #P2.05 [26] M. Šajna, Cycle decompositions. III. Complete graphs and fixed length cycles, J. Comb. Des. 10 (2002), 27–78, doi:10.1002/jcd.1027, https://doi.org/10.1002/jcd.1027. [27] L. Teirlinck, A completion of Lu’s determination of the spectrum for large sets of disjoint Steiner triple systems, J. Comb. Theory Ser. A 57 (1991), 302–305, doi:10.1016/0097-3165(91) 90053-j, https://doi.org/10.1016/0097-3165(91)90053-j. [28] A. Vietri, Cyclic k-cycle systems of order 2kn + k: a solution of the last open cases, J. Comb. Des. 12 (2004), 299–310, doi:10.1002/jcd.20002, https://doi.org/10.1002/ jcd.20002. [29] S.-L. Wu, Cyclic even cycle systems of the complete graph, J. Comb. Des. 20 (2012), 23–29, doi:10.1002/jcd.20310, https://doi.org/10.1002/jcd.20310. [30] S.-L. Wu, Cyclic odd 3K-cycle systems of the complete graph, Taiwanese J. Math. 17 (2013), 1557–1574, doi:10.11650/tjm.17.2013.2703, https://doi.org/10.11650/tjm.17. 2013.2703. [31] S.-L. Wu and H.-L. Fu, Cyclic m-cycle systems with m ≤ 32 or m = 2q with q a prime power, J. Comb. Des. 14 (2006), 66–81, doi:10.1002/jcd.20082, https://doi.org/10.1002/ jcd.20082. [32] S.-L. Wu and H.-L. Fu, Erratum to: Cyclic m-cycle systems with m ≤ 32 or m = 2q with q a prime power, J. Comb. Des. 14 (2006), 167, doi:10.1002/jcd.20100, https://doi.org/ 10.1002/jcd.20100. Appendix We computed sets of mutually orthogonal cyclic ℓ-cycle systems of order n = 2ℓ + 1 for small values of ℓ, and in so doing we empirically determined or bounded µ′(ℓ, 2ℓ + 1) in these cases. Recall from Lemma 6.4 that µ′(ℓ, 2ℓ+ 1) ≤ 2ℓ− 2. Note that for any cyclic ℓ-cycle system of order 2ℓ + 1, the cycles of the system com- prise a single Z2ℓ+1-orbit. To find sets of mutually orthogonal cyclic ℓ-cycle systems of order 2ℓ+ 1, we first determined the orbit for each possible system and then constructed a graph in which each system is represented as a vertex and adjacency denotes orthogonality. Maximum cliques were then sought. The results for 3 ≤ ℓ ≤ 11 are summarised in Table 1. For 9 ≤ ℓ ≤ 11, we found cliques of order 8 but we do not yet know whether larger cliques exist (the computational task becomes increasingly challenging as the number of systems grows). We now present examples of the Z2ℓ+1-orbits for the sets of mutually orthogonal cyclic ℓ-cycle systems of order 2ℓ+ 1 that we found. Each orbit is represented by the differences that occur on the edges of its cycles, using notation from Section 2. ℓ = 3, n = 7 [1, 2,−3], [1,−3, 2] ℓ = 4, n = 9 [1,−2,−3, 4], [1, 4,−3,−2] ℓ = 5, n = 11 [1,−2, 4, 3, 5], [1, 3,−2, 5, 4], [1, 4, 5,−2, 3], [1, 5, 3, 4,−2] A. C. Burgess et al.: Mutually orthogonal cycle systems 19 ℓ n = 2ℓ+ 1 No. of Cyclic Systems µ′(ℓ, 2ℓ+ 1) 3 7 2 2 4 9 6 2 5 11 24 4 6 13 168 5 7 15 1344 8 8 17 11136 8 9 19 128304 ≥ 8 10 21 1504248 ≥ 8 11 23 19665040 ≥ 8 Table 1: Number of mutually orthogonal cyclic ℓ-cycle systems of order 2ℓ+ 1. ℓ = 6, n = 13 [1, 2, 3,−4, 5, 6], [1,−4,−2, 3,−5,−6], [1, 5, 3, 6,−4, 2], [1,−5,−4, 3,−6,−2], [1, 6, 3, 2, 5,−4] ℓ = 7, n = 15 [1, 2, 6,−4,−7,−3, 5], [1,−2,−3,−5,−4, 7, 6], [1, 3, 4,−2, 6,−5,−7], [1,−3, 4, 2,−5,−6, 7], [1, 5,−3,−7,−4, 6, 2], [1, 6, 7,−4,−5,−3,−2], [1, 7,−6,−5, 2, 4,−3], [1,−7,−5, 6,−2, 4, 3] ℓ = 8, n = 17 [1, 2, 3, 4,−6,−7,−5, 8], [1,−2,−3, 8, 5,−6, 4,−7], [1, 3, 7,−8,−6, 2,−4, 5], [1,−3,−5, 6, 4,−8, 7,−2], [1, 4, 5, 2,−3, 6,−7,−8], [1, 5,−7, 6,−8,−3, 2, 4], [1,−6,−8, 2, 5,−4, 7, 3], [1,−8,−7, 5,−3, 4, 2, 6] ℓ = 9, n = 19 [1, 2, 3, 4, 5,−6,−7, 9, 8], [1,−2, 3,−4,−7, 6, 8, 9, 5], [1, 5, 8,−3, 7,−6,−4, 9, 2], [1,−5,−7,−6,−8,−2,−4, 3, 9], [1, 6,−3,−9, 2,−7, 4,−5,−8], [1,−6, 8,−7,−3,−5,−2, 4,−9], [1, 7, 3, 6,−8, 9,−5, 2, 4], [1, 9,−7, 8, 4, 3, 5, 2,−6] ℓ = 10, n = 21 [1, 2, 3, 4, 5,−7, 6, 9,−10, 8], [1,−2, 3,−4, 5,−6, 8,−9,−7,−10], [1, 3,−2,−5,−10, 9,−6,−8, 4,−7], [1,−6,−10, 7,−3, 9,−5,−2,−8,−4], [1, 7,−9,−8, 5, 6, 4, 3, 2, 10], [1,−8,−5, 3,−6,−9, 7,−10, 2, 4], [1, 10, 3, 6,−7, 5,−8,−2, 4, 9], [1,−10, 3, 5,−4,−9,−2,−7, 8,−6] ℓ = 11, n = 23 [1, 2, 3, 4, 5, 6, 7, 8, 9,−10, 11], [1,−2, 3,−4, 5,−6, 7,−11,−10, 9, 8], [1, 3, 2,−4,−5,−11,−6, 10, 8,−7, 9], [1,−3, 10, 6, 4, 7, 9, 11, 8,−2,−5], [1,−4, 8, 6, 3, 5,−9,−2, 10,−11,−7], [1, 5,−11,−8,−3, 9,−7, 2, 6,−4, 10], [1, 10,−7,−8, 3,−5, 9, 4, 6,−11,−2], [1,−11, 5,−7, 4, 2,−9,−6, 8, 10, 3] 20 Ars Math. Contemp. 23 (2023) #P2.05 Below we present examples of mutually orthogonal cyclic 4-cycle systems of orders 17 and 25; these are mentioned in Section 2. ℓ = 4, n = 17 {[1, 2, 3,−6], [4,−5,−7, 8]}, {[1,−2,−3, 4], [5, 8,−7,−6]}, {[1,−3,−8,−7], [2, 4, 5, 6]}, {[1, 4,−7, 2], [3,−5, 8,−6]}, {[1,−4, 8,−5], [2, 7,−3,−6]}, {[1, 5, 2,−8], [3,−4,−6, 7]}, {[1,−5,−3, 7], [2,−6, 8,−4]}, {[1,−6,−3, 8], [2,−4, 7,−5]}, {[1,−7,−8,−3], [2, 6, 5, 4]}, {[1,−8,−6,−4], [2, 5, 3, 7]} ℓ = 4, n = 25 {[1, 2, 3,−6], [4,−5, 12,−11], [7,−8,−9, 10]}, {[1,−2,−3, 4], [5,−6,−7, 8], [9,−10,−11, 12]}, {[1, 3, 4,−8], [2, 5, 7, 11], [6,−9,−10,−12]}, {[1,−3,−4, 6], [2,−5,−7, 10], [8,−11,−9, 12]}, {[1, 4, 2,−7], [3,−5,−9, 11], [6,−8,−10, 12]}, {[1,−4,−2, 5], [3, 6, 7, 9], [8,−12,−11,−10]}, {[1, 5, 3,−9], [2,−4, 10,−8], [6, 12,−7,−11]}, {[1,−5,−3, 7], [2, 6, 4,−12], [8, 11,−10,−9]}, {[1, 7,−10, 2], [3,−11,−4, 12], [5, 9,−8,−6]}, {[1,−7,−8,−11], [2, 12, 5, 6], [3, 10,−4,−9]}, {[1, 8, 4, 12], [2,−10,−6,−11], [3,−7, 9,−5]}, {[1,−8, 11,−4], [2,−12, 3, 7], [5, 10,−6,−9]}, {[1,−9,−3, 11], [2,−6,−4, 8], [5, 12,−10,−7]}, {[1,−10, 11,−2], [3, 8,−5,−6], [4,−7, 12,−9]}, {[1,−11,−12,−3], [2, 8, 10, 5], [4,−6, 9,−7]}, {[1, 12,−3,−10], [2, 7,−5,−4], [6, 11,−9,−8]}, {[1,−12, 8, 3], [2, 9,−4,−7], [5, 11,−6,−10]}