The multicovering radius problem for some types of discrete structures

详细信息    查看全文

• 作者：Alan J. Aw (1)
  
• 关键词：Probabilistic methods ; Coding theory ; Lovász local lemma ; Multicovering radius ; 05D40 ; 94B99
• 刊名：Designs, Codes and Cryptography
• 出版年：2014
• 出版时间：August 2014
• 年：2014
• 卷：72
• 期：2
• 页码：195-209
• 全文大小：
• 参考文献：1. Alon N., Spencer J.: The Probabilistic Method, 2nd edn. Wiley-Interscience (Wiley), New York (2000) CrossRef
  2. Aw A.J., Ku C.Y.: The covering radius problem for sets of 1-factors of the complete uniform hypergraphs. Submitted (2012).
  3. Bollobás B.: Extremal Graph Theory. Dover Publications Inc, New York (2004)
  4. Cameron P., Wanless I.M.: Covering radius for sets of permutations. Disc. Math. 293, 91-09 (2005) CrossRef
  5. Cohen G.D. et?al.: Covering radius—survey and recent results. IEEE Trans. Inform. Theory 31(3), 328-42 (1985) CrossRef
  6. Cohen G.D. et?al.: Covering Codes. North Holland Mathematical Library. Elsevier, Amsterdam (1997)
  7. Colbourn C.J., Klove T., Ling A.C.H.: Permutation arrays for powerline communication and mutually orthogonal Latin squares. IEEE Trans. Inform. Theory 50(2), 1289-291 (2004) CrossRef
  8. Graham, R.L., Grotschel, M., Lovász, L. (eds): Handbook of Combinatorics. Elsevier, Amsterdam (1995)
  9. Hill R.: A First Course in Coding Theory. Oxford University Press Inc, New York (2009)
  10. Jukna S.: Extremal Combinatorics: With Applications in Computer Science. Springer, New York (2001) CrossRef
  11. Keevash P., Ku C.Y.: A random construction for permutation codes and the covering radius. Des. Codes Cryptogr. 41, 79-6 (2006) CrossRef
  12. Keevash P., Ku C.Y.: Personal Communication.
  13. Klapper A.: The multicovering radii of codes. IEEE Trans. Inform. Theory 43, 1372-377 (1997) CrossRef
  14. Quistorff J.: A survey on packing and covering problems in the Hamming permutation space. Electron J. Comb. 13, # A1 (2006)
  15. Vasantha W.B., Selvaraj R.S.: Multi-covering radius for rank metric codes. Electron J. Comb. 16,# R147 (2009)
  
• 作者单位：Alan J. Aw (1)
  
  1. Raffles Science Institute, Raffles Institution, One Raffles Institution Lane, Singapore, S575954, Singapore
  
• ISSN：1573-7586

文摘

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-377, 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-6, 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-6, cf. 2006). We conclude with a discussion of the multicovering radius problem in an even more general context, which offers room for further research.