Lower bounds on covering codes via partition matrices

Let K q ( n , R ) denote the minimal cardinality of a q-ary code of length n and covering radius R. Let σ q ( n , s ; r ) denote the minimal cardinality of a q-ary code of length n, which is s-surjective with radius r. In order to lower-bound K q ( n , n − 2 ) and σ q ( n , s ; s − 2 ) we introduce partition matrices and their transversals. Our approach leads to a short new proof of a classical bound of Rodemich on K q ( n , n − 2 ) and to the new bound K q ( n , n − 2 ) ⩾ 3 q − 2 n + 2 , improving the first iff 5 ⩽ n < q ⩽ 2 n − 4 . We determine K q ( q , q − 2 ) = q − 2 + σ 2 ( q , 2 ; 0 ) if q ⩽ 10 . Moreover, we obtain the new powerful recursive bound K q + 1 ( n + 1 , R + 1 ) ⩾ min { 2 ( q + 1 ) , K q ( n , R ) + 1 } .