Well-spread sequences and edge-labellings with constant Hamilton-weight

Abstract

A sequence (a i) of integers is well-spread if the sums a i +a j, for i<j, are all different. For a fixed positive integer r, let W r (N) denote the maximum integer n for which there exists a well-spread sequence 0≤ a 1 <…<a n ≤ N with a i ≡ a j (b mod r) for all i, j. We give a new proof that W r (N)<(N/r) 1/2 +O((N/r) 1/4); our approach improves a bound of Ruzsa [ Acta.Arith. 65(1993), 259--283] by decreasing the implicit constant, essentially from 4 to √ 3. We apply this result to verify a conjecture of Jones et al. from [ Discuss. Math. Graph Theory 23(2003), 287--307]. The application concerns the growth-rate of the maximum label Λ(n) in a `most-efficient' metric, injective edge-labelling of K n with the property that every Hamilton cycle has the same length; we prove that 2n 2-O(n 3/2)<Λ(n)<2n 2 +O(n 61/40).