Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-13T06:59:55.561Z Has data issue: false hasContentIssue false

Distinct Sums Modulo n and Tree Embeddings

Published online by Cambridge University Press:  14 February 2002

ANDRÉ E. KÉZDY
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY 40292, USA (e-mail: [email protected])
HUNTER S. SNEVILY
Affiliation:
Department of Mathematics, University of Idaho, Moscow, ID 83844, USA (e-mail: [email protected])

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 π ∈ Sk such that the elements aπ(i)+i are all distinct modulo n.

We prove this conjecture when 2k [les ] 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 [les ] 32(2r+4)n2+1.

Type
Research Article
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)