Covering radius for sets of permutations Original Research Article

We study the covering radius of sets of permutations with respect to the Hamming distance. Let image be the smallest number m for which there is a set of m permutations in image with covering radius image. We study image in the general case and also in the case when the set of permutations forms a group. We find image exactly and bounds on image for image. For image 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 Kézdy 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 image, 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 image, the question can be phrased in geometric terms, concerning configurations in the Minkowski plane over image 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.