Mathematics – Combinatorics
Scientific paper
2011-12-08
Mathematics
Combinatorics
Draft (15 pages), to improve on the reader-friendliness of Theorem 4.3
Scientific paper
The covering radius problem, initially studied by coding theorists, investigates the maximum size of a collection of similar structures such that there exists another such structure that shares at most $k$ elements with each structure in the collection. In particular, Klapper in \cite{klapper} describes an even more general problem in coding theory known as the multicovering radius problem in $\mathbf F^n$, where $\mathbf F$ is a field. At the same time, combinatorialists have been exploring the covering radius problem for discrete structures \cite{quistorff}, e.g., collections of permutations (\cite{keevash-ku}) and collections of perfect matchings (\cite{aw-ku}). In this paper, we introduce a multicovering radius problem for both perfect matchings and permutations that is logically consistent with the one introduced in \cite{klapper} but has not been studied hitherto; and provide some elementary and "frequency parameter" type results by means of generalizing the results obtained in \cite{keevash-ku} and \cite{aw-ku}. We use probabilistic tools, notably the Lov\'asz local lemma, to establish these new results. We conclude with a discussion of a multicovering radius problem for other types of discrete structures, notably sets of positive integers, which offers room for further research.
No associations
LandOfFree
The multicovering radius problem for some types of discrete structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The multicovering radius problem for some types of discrete structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The multicovering radius problem for some types of discrete structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-548730