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.
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 language | English |
---|---|
Article number | 105734 |
Journal | Journal of Combinatorial Theory, Series A |
Volume | 196 |
Early online date | 26 Jan 2023 |
DOIs | |
Publication status | E-pub ahead of print - 26 Jan 2023 |