Permutations that separate close elements

Abstract: Let

n

be a fixed integer with

n g e q 2

. For

i, j i n m a t h b b Z_{n}

, define

| | i, j | |_{n}

to be the distance between

i

and

j

when the elements of

m a t h b b Z_{n}

are written in a cycle. So

. For positive integers

s

and

k

, the permutation

p i : m a t h b b Z_{n} i g h t a r r o w m a t h b b Z_{n}

is emph{

(s, k)

-clash-free} if

| | p i (i), p i (j) | |_{n} g e q k

whenever

| | i, j | |_{n} < s

with

i o t = j

. So an

(s, k)

-clash-free permutation

p i

can be thought of as moving every close pair of elements of

m a t h b b Z_{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 i m e s k

rectangles on an

n i m e s n

torus, whose centres have distinct integer

x

-coordinates and distinct integer

y

-coordinates. For positive integers

n

and

k

with

k < n

, let

s i g m a (n, k)

be the largest value of

s

such that an

(s, k)

-clash-free permutation on

m a t h b b Z_{n}

exists. In a recent paper, Mammoliti and Simpson conjectured that [ lfloor (n-1)/k floor-1leq sigma(n,k)leq lfloor (n-1)/k floor ] for all integers

n

and

k

with

k < n

. The paper establishes this conjecture, by explicitly constructing an

(s, k)

-clash-free permutation on

m a t h b b Z_{n}

with

s = l f l o o r (n - 1) / k f l o o r - 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.

This page was built for publication: Permutations that separate close elements