Covering radius in the Hamming permutation space

Abstract: Let

m a t h c a l S_{n}

denote the set of permutations of

1, 2, d o t s, n

. The function

f (n, s)

is defined to be the minimum size of a subset

S s u b s e t e q m a t h c a l S_{n}

with the property that for any

h o i n m a t h c a l S_{n}

there exists some

s i g m a i n S

such that the Hamming distance between

h o

and

s i g m a

is at most

n - s

. The value of

f (n, 2)

is the subject of a conjecture by K'ezdy and Snevily, which implies several famous conjectures about latin squares. We prove that the odd

n

case of the K'ezdy-Snevily Conjecture implies the whole conjecture. We also show that

f (n, 2) > 3 n / 4

for all

n

, that

s! < f (n, s) < 3 s! (n - s) l o g n

for

1 l e q s l e q n - 2

and that [f(n,s)>leftlfloor frac{2+sqrt{2s-2}}{2} ight floor frac{n}{2}] if

s g e q 3

.

Recommendations

Cites Work

Cited In (7)

This page was built for publication: Covering radius in the Hamming permutation space