Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Covering radius for sets of permutations

Cameron, PJ and Wanless, IM (2005). Covering radius for sets of permutations. Discrete Mathematics,293(1-3):91-109.

Document type: Journal Article
Citation counts: Scopus Citation Count Cited 10 times in Scopus Article | Citations

Google Scholar Search Google Scholar

Title Covering radius for sets of permutations
Author Cameron, PJ
Wanless, IM
Journal Name Discrete Mathematics
Publication Date 2005
Volume Number 293
Issue Number 1-3
ISSN 0012-365X   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-17444370932
Start Page 91
End Page 109
Total Pages 19
Place of Publication Netherlands
Publisher Elsevier
HERDC Category C1 - Journal Article (DEST)
Abstract 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.
Keywords permutations
covering radius
dominating sets
multiply transitive groups
latin squares
affine planes
minkowski planes
steiner triple systems
DOI http://dx.doi.org/10.1016/j.disc.2004.08.024   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 28 Abstract Views  -  Detailed Statistics
Created: Fri, 12 Sep 2008, 08:35:25 CST by Administrator