Lower bounds on covering codes via partition matrices (Q1003655)

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\).