Covering radius for sets of permutations (Q1779486): Difference between revisions

The authors study the covering radius of sets of permutations with respect to the Hamming distance. In particular, they define \(f(n,s)\) to be the smallest integer \(m\) for which there is a set of \(m\) permutations in \(S_n\) with covering radius \(r \leq n-s\). The authors find an exact formula for \(f(n,1)\) and bounds on \(f(n,s)\) for \(s>1\). In the case when the set of permutations forms a group, they give necessary and sufficient conditions for the covering radius to be exactly \(n\). They also provide some results on the covering radius for several specific groups.