Distinct Sums Modulo n and Tree Embeddings
In this paper we are concerned with the following conjecture.
Conjecture. For any positive integers n and k satisfying k < n, and any sequence a1, a2, … ak of not necessarily distinct elements of Zn, there exists a permutation π [set membership] Sk such that the elements aπ(i)+i are all distinct modulo n.
We prove this conjecture when 2k [less-than-or-eq, slant] n+1. We then apply this result to tree embeddings. Specifically, we show that, if T is a tree with n edges and radius r, then T decomposes Kt for some t [less-than-or-eq, slant] 32(2r+4)n2+1.(Received July 11 2000)
(Revised March 6 2001)