<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue4" %>
An Enumerative Geometry for Magic and Magilatin Labellings
Matthias Beck1 and Thomas Zaslavsky2
1Department of Mathematics, San Francisco State University, 1600 Holloway Avenue, San Francisco, CA 94132, USA
beck@math.sfsu.edu
2Department of Mathematical Sciences, State University of New York at Binghamton, Binghamton, NY 13902-6000, USA
zaslav@math.binghamton.edu
Annals of Combinatorics 10 (4) p.395-498 December, 2006
AMS Subject Classification: 05A15, 05C78, 52B20, 52C35
Abstract:
A magic labelling of a set system is a labelling of its points by distinct positive integers so that every set of the system has the same sum, the magic sum. Examples are magic squares (the sets are the rows, columns, and diagonals) and semimagic squares (the same, but without the diagonals). A magilatin labelling is like a magic labelling but the values need be distinct only within each set. We show that the number of n×n magic or magilatin labellings is a quasipolynomial function of the magic sum, and also of an upper bound on the entries in the square. Our results differ from previous ones because we require that the entries in the square all be different from each other, and because we derive our results not by ad hoc reasoning but from a general theory of counting lattice points in rational inside-out polytopes. We also generalize from set systems to rational linear forms.
Keywords: magic labelling, magic square, semimagic labelling, semimagic square, magic graph, Latin square, magilatin labelling, magilatin square, covering clutter, lattice-point counting, rational inside-out convex polytope, arrangement of hyperplanes, Ehrhart theory

References:

1. W.S. Andrews, Magic Squares and Cubes (with chapters by other writers), 2nd Ed., Dover Publications, New York, 1960.

2. W.W. Rouse Ball, Mathematical Recreations and Essays, 11th Ed., revised by H.S.M. Coxeter, Macmillan, London, 1939.

3. M. Beck, M. Cohen, J. Cuomo, and P. Gribelyuk, The number of “magic” squares and hypercubes, Amer. Math. Monthly 110 (8) (2003) 707-717.

4. M. Beck and T. Zaslavsky, Inside-out polytopes, Adv. Math. 205 (1) (2006) 134-162.

5. M. Beck and T. Zaslavsky, Six little squares and how their numbers grow, in preparation.

6. W.H. Benson and O. Jacoby, New Recreations with Magic Squares, Dover Publications, New York, 1976.

7. S. Cammann, Old Chinese magic squares, Sinologica 7 (1962) 14-53.

8. S. Cammann, Islamic and Indian magic squares, Parts I and II, History of Religions 8 (1968/1969) 181-209, 271-299.

9. E. Ehrhart, Sur un problème de géometrie diophantienne linéaire. I: Polyèdres et réseaux. II: Systèmes diophantiens linéaires, J. Reine Angew. Math. 226 (1967) 1-29; 227 (1967) 25-49.

10. E. Ehrhart, Sur les carrés magiques, C. R. Acad. Sci. Paris Sér. A-B 277 (1973) A651-A654.

11. J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 5 (2005) #DS6, 148 pp.

12. G.-C. Rota, On the foundations of combinatorial theory I: Theory of Möbius functions, Z. Wahrsch. 2 (1964) 340-368.

13. Society of Go Philosophers of the North River, Magic in mathematics: A methodological and metalogical examination, Rep. S.G.P.N.R. 96 (2) (1992).

14. R.P. Stanley, Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973) 607-632.

15. R.P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171-178.

16. R.P. Stanley, Enumerative Combinatorics, Vol. I,Wadsworth & Brooks/Cole, Monterey, CA, 1986.

17. G. Xin, Constructing all magic squares of order three, arXiv: math.CO/0409468.

18. C. Zaslavsky, Africa Counts: Number and Pattern in African Culture, Prindle, Weber & Schmidt, Boston, 1973.