Combinatorics, Probability & Computing

Table of Contents - 2002 - Volume 11, Issue 01  


Distinct Sums Modulo n and Tree Embeddings

ANDRÉ E. KÉZDY a1 and HUNTER S. SNEVILY a2
a1 Department of Mathematics, University of Louisville, Louisville, KY 40292, USA (e-mail: kezdy@louisville.edu)
a2 Department of Mathematics, University of Idaho, Moscow, ID 83844, USA (e-mail: snevily@uidaho.edu)

Abstract

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)