\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Wolfgang Haas, Immanuel Halupczok and Jan-Christoph Schlage-Puchta}
%
%
\medskip
\noindent
%
%
{\bf Lower Bounds for $q$-ary Codes with Large Covering Radius}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $K_q(n,R)$ denote the minimal cardinality of a $q$-ary code of
length $n$ and covering radius $R$. Recently the authors gave a new
proof of a classical lower bound of Rodemich on $K_q(n,n-2)$ by the
use of partition matrices and their transversals. In this paper we
show that, in contrast to Rodemich's original proof, the method
generalizes to lower-bound $K_q(n,n-k)$ for any $k>2$.
The approach is best-understood in terms of a game where a winning strategy
for one of the players implies the non-existence of a code.
This proves to be by far the
most efficient method presently known to lower-bound $K_q(n,R)$ for
large $R$ (i.e. small $k$). One instance: the trivial
sphere-covering bound $K_{12}(7,3)\geq 729$, the previously best
bound $K_{12}(7,3)\geq 732$ and the new bound $K_{12}(7,3)\geq 878$.
\bye