Permutations that Separate Close Elements, and Rectangle Packings in the Torus - Blackburn, Simon R.; Etzion, Tuvi (The Electronic Journal of Combinatorics, 2024)
Let n, s and k be positive integers. For distinct i,jZ_n, define ||i,j||_n to be the distance between i and j when the elements of Z_n are written in a circle. So \[ ||i,j||_n={(i-j)n,(j-i)n}. \] A permutation π:Z_n→Z_n is (s,k)-clash-free if ||π(i),π(j)||_n≥ k whenever ||i,j||_n<s. So an (s,k)-clash-free permutation moves every pair of close elements (at distance less than s) to a pair of elements at large distance (at distance at least k). The notion of an (s,k)-clash-free permutation can be reformulated in terms of certain packings of s× k rectangles on an n× n torus. For integers n and k with 1≤ k<n, let σ(n,k) be the largest value of s such that an (s,k)-clash-free permutation of Z_n exists. Strengthening a recent paper of Blackburn, which proved a conjecture of Mammoliti and Simpson, we determine the value of σ(n,k) in all cases.