Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-12-01T08:54:00.864Z Has data issue: false hasContentIssue false
  • English
  • Français

Distinct Sums Modulo n and Tree Embeddings

Published online by Cambridge University Press:  14 February 2002

ANDRÉ E. KÉZDY  and
HUNTER S. SNEVILY
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])
Get access Rights & Permissions [Opens in a new window]

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
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 1 , January 2002 , pp. 35 - 42
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.)