A Covering Problem for Tori

Patric R.J. Östergård and Taneli Riihonen

Department of Electrical and
Communications Engineering, Helsinki University of Technology
P.O. Box 3000, 02015 HUT, Finland

{patric.ostergard, taneli.riihonen}@hut.fi

Annals of Combinatorics 7 (3) p.357-363 September, 2003

Abstract:

The problem of covering an
*n*-dimensional
torus with *n*-dimensional grid graphs
is studied. This is the dual problem of a packing
problem concerning the capacity of a graph, which
has been studied in information theory. It is related
to several other problems as well, including
weighted coverings, Keller's cube-tiling problem,
and the recreational problem of
how to obtain zero correct predictions in the football
pools. Motivated by the last problem, bounds on the
minimum size of such coverings are tabulated
for *q* = 3, *p* = 2, and small *n*.

References:

1. L.D. Baumert, R.J. McEliece, E. Rodemich, H.C. Rumsey Jr., R. Stanley, and H. Taylor, A combinatorial packing problem, In: Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970, Computers in Algebra and Number Theory, G. Birkhoff and M. Hall Jr., Eds., Amer. Math. Soc., Providence, 1971, pp. 97–108.

2. G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.

3. T.M. Cover and J.A. Thomas, Elements of Information Theory, Wiley, New York, 1991.

4. H. Hämäläinen, I. Honkala, S. Litsyn, and P.östergård, *Football pools ―a game for mathematicians*,
Amer. Math. Monthly 102 (1995) 579–588.

5. A. Hertz, E. Taillard, and D. de Werra, Tabu search, In: Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra, Eds., Wiley, Chichester, 1997, pp. 121–136.

6. I.S. Honkala and P.R.J. Östergård, Code design, In: Local Search in Combinatorial Optimization, E. Aarts and J.K. Lenstra, Eds., Wiley, Chichester, 1997, pp. 441–456.

7. J.C. Lagarias and P.W. Shor, Keller's cube-tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. (N.S.) 27 (1992) 279–283.

8. L. Lovsz, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979) 1–7.

9. P.R.J. Östergård, Constructing covering codes by tabu search, J. Combin. Des. 5 (1997) 71–80.

10. P.R.J. Östergård andW.D.Weakley, Constructing covering codes with given automorphisms, Des. Codes Cryptogr. 16 (1999) 65–73.

11. C.E. Shannon, The zero-error capacity of a noisy channe, IRE Trans. Inform. Theory 2 (1956) 8–19.

12. A. Vesel, The independence number of the strong product of cycles Comput. Math. Appl. 36 (7) (1998) 9–21.

13. A. Vesel and J. Žerovnik, Improved lower bound on the Shannon capacity of C_{7}, Inform.
Process. Lett. 81 (2002) 277–282.