Permutations that separate close elements

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

Abstract

Let n be a fixed integer with n≥2. For i,j∈ℤn, define ||i,j||n to be the distance between i and j when the elements of ℤn are written in a cycle. So ||i,j||n=min{(i−j)modn,(j−i)modn}. For positive integers s and k, the permutation π:ℤn→ℤn is \emph{(s,k)-clash-free} if ||π(i),π(j)||n≥k whenever ||i,j||n<s with i≠j. So an (s,k)-clash-free permutation π can be thought of as moving every close pair of elements of ℤn to a pair at large distance. More geometrically, the existence of an (s,k)-clash-free permutation is equivalent to the existence of a set of n non-overlapping s×k rectangles on an n×n torus, whose centres have distinct integer x-coordinates and distinct integer y-coordinates.
For positive integers n and k with k<n, let σ(n,k) be the largest value of s such that an (s,k)-clash-free permutation on ℤn exists. In a recent paper, Mammoliti and Simpson conjectured that
⌊(n−1)/k⌋−1≤σ(n,k)≤⌊(n−1)/k⌋
for all integers n and k with k<n. The paper establishes this conjecture, by explicitly constructing an (s,k)-clash-free permutation on ℤn with s=⌊(n−1)/k⌋−1. Indeed, this construction is used to establish a more general conjecture of Mammoliti and Simpson, where for some fixed integer r we require every point on the torus to be contained in the interior of at most r rectangles.
Original languageEnglish
JournalJournal of Combinatorial Theory, Series A
Publication statusAccepted/In press - 9 Jan 2023

Cite this