More coverings by rook domains (Q789394): Difference between revisions

Let \(V^ n\!_ k\) denote the set of all \(n\)-tuples \(x=(x_ 1,x_ 2,...,x_ n)\) with \(x_ i\in\mathbb R_ k\). Define \(\sigma (n,k)\) to be the minimum size of a set \(W\subseteq V^ n_ k\) such that for each \(x\) in \(V^ n_ k\), there is an element in \(W\) that differs from \(x\) in at most one coordinate. \textit{H. J. L. Kamps} and \textit{J. H. van Lint} [Combinat. Theory Appl., Colloq. Math. Soc. János Bolyai 4, 679--685 (1970; Zbl 0231.05030)] proved: \(\sigma(9,3)\leq 2.3^ 6\). Their method is generalized and this leads to the result \(\sigma(n,p)\leq(p-t+1)p^{n- r},\) if \(p\) is a prime and \(n=1+t(p^ r-1)/(p-1)\) for some integers \(t\) and \(r\). \textit{E. R. Rodemich} [J. Comb. Theory 9, 117--128 (1970; Zbl 0219.05013)] proved that \(\sigma(n,k)\geq k^{n-1}/(n-1)\) if \(k\geq n\). The authors now prove that: \(\sigma(n,kt)\leq \sigma(n,k)t^{n-1}\) and as a corollary \(\sigma(q+1,qt)=q^{q-1}t^ q\) if \(q\) is a prime power (using Rodemich's result). It is also shown that \(\sigma(10,3)\leq 5,3^ 6\). New bounds for \(\sigma (6,3)\), \(\sigma (7,3)\), and \(\sigma (8,3)\) were obtained recently by \textit{E. W. Weber} [J. Comb. Theory, Ser. A 35, 106--108 (1983; Zbl 0526.05019)] and \textit{H. Fernandes} and \textit{E. Rechtschaffen} [ ibid. 35, 109--114 (1983; Zbl 0526.05020)].