Sums and differences along Hamiltonian cycles

Vsevolod F. Lev^{1}

Department of Mathematics The University of Haifa at Oranim Tivon, Israel

Abstract

Given a finite abelian group G, consider the complete graph on the set of all elements of G. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of distinct sums that can emerge in this way? What is the expected number of distinct sums if the cycle is chosen randomly? How the answers change if an orientation is given to the cycle and differences (instead of sums) are computed? We give complete solutions to some of these problems and establish reasonably sharp estimates for the rest.

Keywords: Rainbow-sum cycles, rainbow-difference paths, directed terraces, sequenceable groups, harmonious groups, addition Cayley graphs.

1 Introduction

For a finite abelian group G, by C(G) we denote the set of all Hamiltonian cycles in the complete digraph on the vertex set G; thus, C(G) is empty if G

1 Email: seva@math.haifa.ac.il

is trivial and |C(G)| = (|G| − 1)! otherwise. Given a cycle C ∈ C(G), label each edge (g_{1}, g_{2}) ∈ C with the sum g_{1} + g_{2} and consider the set S(C) ⊆ G of all labels along C. Now let

σ_{max}(G) := max{|S(C)|: C ∈ C(G)},
σ_{min}(G) := min{|S(C)|: C ∈ C(G)},

and assuming that C ∈ C(G) is chosen randomly,

σ_{rnd}(G) := E (|S(C)|).

Similarly, labeling each (directed) edge (g_{1}, g_{2}) ∈ C with the difference g_{2} −g_{1}, consider the set D(C) ⊆ G of all labels along C, and let

δ_{max}(G) := max{|D(C)|: C ∈ C(G)},
δ_{min}(G) := min{|D(C)|: C ∈ C(G)},

and (chosing C ∈ C(G) at random),

δ_{rnd}(G) := E (|D(C)|).

We assume that min ∅ = max ∅ = 0 in the definitions above; thus, if G is trivial, then σ_{max}(G) = σ_{min}(G) = δ_{max}(G) = δ_{min}(G) = 0, while σ_{rnd}(G) and δ_{rnd}(G) are undefined. Also, if |G| = 2, then σ_{max}(G) = σ_{min}(G) = δ_{max}(G) = δ_{min}(G) = σ_{rnd}(G) = δ_{rnd}(G) = 1.

Occasionally, we will consider Hamiltonian cycles on subsets of finite abelian groups, as well as Hamiltonian paths on finite abelian groups or their subsets. The definitions of S(C) and D(C) are carried without any modification onto the case where C is a Hamiltonian cycle or path on a finite subset of an additively written group.

Both cycles and paths on the set A will be written as C = (a_{1}, …, a_{|A|}), where the components of C list the elements of A; clearly, each Hamiltonian path on A has a unique representation of this sort, and each cycle has |A| representations.

In connection with the quantities σ_{max}(G) and δ_{max}(G) we will be interested in Hamiltonian cycles and paths such that all sums (differences) of two consecutive elements along the cycle or path are pairwise distinct; that is, |S(C)| = |A| (respectively, |D(C)| = |A|) for a cycle and |S(C)| = |A| − 1 (respectively, |D(C)| = |A| − 1) for a path on the set A. We call such cycles and paths rainbow-sum (respectively, rainbow-difference) and use abbreviations like “RS-cycle” or “RD-path”. Under various names such cycles and paths have been studied by a number of authors; some references are given in the next section.

2 Summary of results

We present here our principal results and briefly comment on the proofs; the complete proofs will be presented in a separate paper.

The smallest possible number of differences along a Hamiltonian cycle can be determined precisely.

Theorem 2.1 For any finite abelian group G we have δ_{min}(G) = rk(G).

For the proof write n := |G| and notice that if C = (0, g_{1}, …, g_{n−1}) ∈ C(G), then any element of G is representable as a sum of elements of D(C):

g_{i} = (g_{i} − g_{i−1}) + ... + (g_{2} − g_{1}) + (g_{1} − 0); i ∈ [1, n − 1].

It follows that D(C) generates G whence |D(C)| ≥ rk(G) and therefore δ_{min}(G) ≥ rk(G). On the other hand, using induction by rk(G), we were able to construct explicitly a cycle C ∈ C(G) with |D(C)| = rk(G).

The situation with the largest possible number of differences is subtler and for some groups there is still room for improvement.

Recall, that an involution of a group is a group element of order 2. It is easily seen that a finite abelian group has exactly one involution if and only if it has exactly one invariant factor of even order; another necessary and sufficient condition is that the sum of all group elements is distinct from 0.

Theorem 2.2 For any finite non-trivial abelian group G we have

δ_{max}(G) ≤ \begin{cases}|G| − 1 & if G is one-involution, \\ |G| − 2 & if G is not one-involution. \end{cases}

Indeed, equality holds for all groups G with the possible exception of those, whose Sylow 2-subgroup is non-cyclic of order 8.

The proof of Theorem 2.2 is based on the results of Gordon [4] and Headley [6] asserting that (i) if G is one-involution, then G possesses an RD-path; (ii) if G is not one-involution and Sylow 2-subgroup of G is not of order 8, then the set of non-zero elements of G possesses an RD-cycle. (These results are based on earlier work of Friedlander, Gordon, and Miller [3]). The question of whether the requirement that G is not one-involution alone, without any extra assumptions, ensures the existence of an RD-cycle on the set of non-zero elements of G, to our knowledge is open. Answering it in the affirmative would show that in the estimate of Theorem 2.2 equality is actually attained for all finite non-trivial abelian groups G.

For those exceptional groups, not covered by the second assertion of Theorem 2.2, a lower bound for δ_{max}(G) is immediate from our next result.

Theorem 2.3 For any finite non-trivial abelian group G we have

δ_{rnd}(G) = (1 − e^{−1})|G| + O(1),

with an absolute implicit constant.

Observe that the expression (1 − e^{−1})|G| + O(1) is not at all surprising in this context, giving the expected number of pairwise distinct elements of G, appearing in the sequence of |G| randomly and independently chosen elements.

The proofs of Theorems 2.3 and 2.7 (stated below) amount to counting, for every g ∈ G, the number of Hamiltonian cycles C ∈ C(G) with g ∈ S(C) and g ∈ D(C), respectively. This involves a combinatorial argument, employing a nested application of the inclusion-exclusion principle.

For a subset S of a finite abelian group G, consider the graph with the vertex set G and the edge set {(g′, g′′) ∈ G × G: g′ + g′′ ∈ S}. We denote this graph by Cay_{G}^{+}(S) and call it the addition Cayley graph, induced on G by S. Addition Cayley graphs received very little attention in the literature; the two papers to mention are [4], where the clique number of the random addition Cayley graph is studied, and [2], where hamiltonicity of addition Cayley graphs is investigated in the special case that S does not contain elements of the form 2g with g ∈ G. The latter paper is particularly relevant in our context: in a somewhat unexpected way, it turns out that the quantity σ_{min}(G) is tightly related to hamiltonicity of the graphs Cay_{G}^{+}(S). Specifically, if C ∈ C(G), then C is a Hamiltonian cycle in Cay_{G}^{+}(S(C)); conversely, if S ⊆ G and C is a Hamiltonian cycle in Cay_{G}^{+}(S), then S(C) ⊆ S. (We identify graphs with the digraphs, obtained by replacing each undirected edge with the pair of corresponding directed edges. Thus, for instance, if |G| = 2 and S contains the non-zero element of G, then Cay_{G}^{+}(S) is considered Hamiltonian.) It follows that σ_{min}(G) is the minimum size of a subset S ⊆ G such that Cay_{G}^{+}(S) is Hamiltonian. We remark that hamiltonicity of “conventional” Cayley graphs was intensively studied and in particular, it is well-known that any connected Cayley graph on a finite abelian group with at least three elements is Hamiltonian; see [8]. However, apart from the results of [2], nothing seems to be known on hamiltonicity of addition Cayley graphs. We establish some properties of the graphs Cay_{G}^{+}(S) and as a corollary determine the value of σ_{min}(G) precisely if G is of even order, and obtain reasonable estimates if G is of odd order.

Theorem 2.4 Let G be a finite non-trivial abelian group. If |G| is even and G is of type (m_{1}, …, m_{rk(G)}), then

σ_{min}(G) = \begin{cases}rk(G) & if m_{1} = 2, \\ rk(G) + 1 & if m_{1} > 2. \end{cases}

If |G| is odd, then

rk(G) + 1 ≤ σ_{min}(G) ≤ 2 rk(G) + 1.

Theorem 2.4 shows that σ_{min}(G) = 2 if G is cyclic of even order |G| ≥ 4, and σ_{min}(G) ∈ {2, 3} if G is cyclic of odd order. Indeed, we were able to find σ_{min}(G) for cyclic groups G of odd order, too.

Theorem 2.5 If G is cyclic of order |G| ≥ 3, then

σ_{min}(G) = \begin{cases}2 & if |G| is even, \\ 3 & if |G| is odd. \end{cases}

Computations seem to suggest that if rk(G) = 2 and |G| ≠ 9 is odd, then σ_{min}(G) = 3. One can speculate that, indeed, σ_{min}(G) = rk(G) + 1 for all non-cyclic finite abelian groups G of odd order, with a “small” number of exceptions.

Our next theorem establishes the largest possible number of sums along a Hamiltonian cycle.

Theorem 2.6 For any finite non-trivial abelian group G we have

σ_{max}(G) = \begin{cases}|G| & if G is neither one-involution, \\ & nor of exponent 2, \\ |G| − 1 & if G is one-involution, \\ |G| − 2 & if G is of exponent 2 and |G| > 2. \end{cases}

The proof of Theorem 2.6 is based on (i) a theorem due to Beals, Gallian, Headley, and Jungreis (see [1]), claiming that if G is a finite abelian group, which is neither a one-involution group, nor an elementary 2-group, then G possesses an RS-cycle; (ii) an original construction of an RS-path on every finite abelian one-involution group G.

It is worth mentioning that Theorem 2.6 bears relation with Latin transversals in Cayley tables, as we now explain. Let G be a finite abelian group. Does the Cayley table of G have a Latin transversal? In other words, do there exist two permutations (g′_{1}, …, g′_{|G|}) and (g′′_{1}, …, g′′_{|G|}) of the elements of G such that (g′_{1} + g′′_{1}, …, g′_{|G|} + g′′_{|G|}) is also a permutation? It is easily seen that if the answer is positive, then the elements of G sum to 0, whence G is not one-involution; on the other hand, it was shown in [10] (see also [13] where this was independently rediscovered) that this condition is also sufficient. Notice the connection with Snevily’s conjecture [12], which is that any square sub-table of the Cayley table of a finite abelian group of odd order possesses a Latin transversal. Clearly, G has an RS-cycle if and only if its Cayley table has a Latin transversal of some special sort; namely, one with g′′_{1} = g′_{2}, g′′_{2} = g′_{3} , …, g′′_{n} = g′_{1}.

Our last theorem is worth comparison with Theorem 2.3.

Theorem 2.7 For any finite non-trivial abelian group G we have

σ_{rnd}(G) = (1 − e^{−1})|G| + O(1),

with an absolute implicit constant.

References

[1] R. Beals, J.A. Gallian, P. Headley, and D. Jungreis, Harmonious groups, J. Comb. Theory, Series A 56 (1991), 223–238.

[2] B. Cheyne, V. Gupta, and C. Wheeler, Hamilton Cycles in Addition Graphs, Rose-Hulman Undergraduate Math. Journal 1 (4) (2003) (electronic).

[3] R.J. Friedlander, B. Gordon, and M.D. Miller, On a group sequencing problem of Ringel, Congr. Numer. 21 (1978), 307–321.

[4] B. Gordon, Sequences in groups with distinct partial products, Pacific J. Math. 11 (1961), 1309–1313.

[5] B. Green, Counting sets with small sumset, and the clique number of random Cayley graphs, Combinatorica 25 (3) (2005), 307–326.

[6] P. Headley, R-sequenceability and R*-sequenceability of Abelian 2-groups, Discrete Math. 131 (1–3) (1994), 345–350.

[7] A.D. Keedwell, Complete mappings and sequencings of finite groups, “CRC Handbook of Combinatorial Designs” (C.J Colbourn and J.H Dinitz eds.), CRC Press 1996, 246–253.

[8] D. Marušič, Hamiltonian circuits in Cayley graphs, Discrete Math. 46 (1) (1983), 49–54.

[9] M.A. Ollis, On terraces for abelian groups, Discrete Mathematics 305 (2005), 250–263.

[10] L.J. Paige, A note on finite Abelian groups, Bull. Amer. Math. Soc. 53 (1947), 590–593.

[11] L.J. Paige, Complete mappings of finite groups, Pacific J. Math. 1 (1951), 111–116.

[12] H.S. Snevily, Unsolved Problems: The Cayley Addition Table of ℤ_{n}, Amer. Math. Monthly 106 (6) (1999), 584–585.

[13] J. Surányi, A certain way of presenting finite abelian groups [Hungarian], Mat. Lapok 23 (1972), 257–259 (1974).