Lower bounds on covering codes via partition matrices
type: Item
instance of: scholarly article
title: Lower bounds on covering codes via partition matrices
zbMATH Open document ID: 1160.94020
author: Wolfgang Haas
author: Jan-Christoph Schlage-Puchta
author: Jörn Quistorff
published in: Journal of Combinatorial Theory. Series A
publication date: 2009-03-04T00:00:00Z
review text: The minimum cardinality of a \(q\)-ary code of length \(n\) and covering radius \(R\) is denoted by \(K_q(n,R)\). By utilizing the framework of partition matrices [\textit{W. Benz}, Combinatorics '90, Proc. Conf., Gaeta/Italy 1990, Ann. Discrete Math. 52, 25--36 (1992; Zbl 0768.51012)] the authors obtain general lower bounds on \(K_q(n,n-2)\), improving on the bound by \textit{E. R. Rodemich} [J. Comb. Theory 9, 117--128 (1970; Zbl 0219.05013)] in several cases. The following new bound is also proved: \(K_{q+1}(n+1,R+1) \geq \min\{2(q+1),K_q(n,R)+1\}\). The authors tabulate 36 explicit new lower bounds on \(K_q(n,R)\) for \(5 \leq q \leq 21\), \(5 \leq n \leq 10\), and \(n-3 \leq R \leq n-2\).
reviewed by: Patric R. J. Östergård
Mathematics Subject Classification ID: 94B75
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 5523144
zbMATH Keywords: covering codes
zbMATH Keywords: partition matrices
zbMATH Keywords: Rodemich bound
zbMATH Keywords: surjective codes
MaRDI profile type: Publication
full work available at URL: j.jcta.2008.06.008
OpenAlex ID: W2023908631
cites work: Q4028416
cites work: A note on bounds for q-ary covering codes
cites work: Q4342497
cites work: On the covering radius of small codes
cites work: Bounds for covering codes over large alphabets
cites work: Further results on the covering radius of small codes
cites work: Families of \(k\)-independent sets
cites work: Q4307539
cites work: Coverings by rook domains
DOI: 10.1016/J.JCTA.2008.06.008
description: scientific article; zbMATH DE number 5523144