We study the covering radius of sets of permutations with respect to the Hamming distance. Let f (n, s) be the smallest number m for which there is a set of m permutations in S-n with covering radius r 1. For s = 2 our bounds are linear in n. This case relates to classical conjectures by Ryser and Brualdi on transversals of Latin squares and to more recent work by Kezdy and Snevily. We discuss a flaw in Derienko's published proof of Brualdi's conjecture. We also show that every Latin square contains a set of entries which meets each row and column exactly once while using no symbol more than twice. In the case where the permutations form a group, we give necessary and sufficient conditions for the covering radius to be exactly n. If the group is t-transitive, then its covering radius is at most n - t, and we give a partial determination of groups meeting this bound. We give some results on the covering radius of specific groups. For the group PGL(2, q), the question can be phrased in geometric terms, concerning configurations in the Minkowski plane over GF(q) meeting every generator once and every conic in at most s points, where s is as small as possible. We give an exact answer except in the case where q is congruent to 1 mod 6. The paper concludes with some remarks about the relation between packing and covering radii for permutations. (c) 2005 Elsevier B.V. All rights reserved.
Cited 
