The multicovering radius problem for some types of discrete structures

The covering radius problem is a question in coding theory concerned with finding the minimum radius r such that, given a code that is a subset of an underlying metric space, balls of radius r over its code words cover the entire metric space. Klapper (IEEE Trans. Inform. Theory 43:1372–1377, 1997) introduced a code parameter, called the multicovering radius, which is a generalization of the covering radius. In this paper, we introduce an analogue of the multicovering radius for permutation codes (Des. Codes Cryptogr. 41:79–86, cf. 2006) and for codes of perfect matchings (cf. 2012). We apply probabilistic tools to give some lower bounds on the multicovering radii of these codes. In the process of obtaining these results, we also correct an error in the proof of the lower bound of the covering radius that appeared in (Des. Codes Cryptogr. 41:79–86, cf. 2006). We conclude with a discussion of the multicovering radius problem in an even more general context, which offers room for further research.