<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue3" %>
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
AMS Subject Classification: 05C70, 94B25
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.
Keywords: covering, grid graph, tabu search, ternary code, torus


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 C7, Inform. Process. Lett. 81 (2002) 277–282.