Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site lasspvax.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!vax135!cornell!lasspvax!rokhsar
From: rokhsar@lasspvax.UUCP (Dan Rokhsar)
Newsgroups: net.math
Subject: Labeling a Lattice
Message-ID: <325@lasspvax.UUCP>
Date: Mon, 6-May-85 13:18:29 EDT
Article-I.D.: lasspvax.325
Posted: Mon May  6 13:18:29 1985
Date-Received: Sun, 12-May-85 04:47:54 EDT
Reply-To: rokhsar@lasspvax.UUCP (Dan Rokhsar)
Organization: LASSP, Cornell University
Lines: 44

Newsgroup: net.math
Subject: Labeling a lattice
Expires: 
References: 
Sender: 
Reply-To: rokhsar@lasspvax.UUCP (Dan Rokhsar)
Followup-To: 
Distribution: 
Organization: Laboratory of Atomic and Solid State Physics, Cornell University
Keywords: 

Here's a problem related to the "can we map a square to an interval" problem, 
but with a twist.

Consider an N x N square lattice (the generalization to higher dimensions is
trivial).  We wish to assign a unique integer between 1 and N^2 to each
lattice site, so that the maximum difference between adjacent labels is
minimized.  Boundary conditions can be either free or periodic.

Questions:
	1.	How does the minimum maximal difference (MMD) vary with
		the size of the square?  The dimension of the hypercube?
	2.	Can we find a rigorous lower bound to the MMD? (by constructing
		a labeling, we have found that MMD <= (D N)^(D-1) in D
		dimensions, and by considering the best labeling of a
		single point and its neighbors, MMD >= (2^D) : a Monte-
		Carlo approach has yielded an ordering qualitatively similar
		to the one that gives (D N)^(D-1), at least in 2 dimensions)
	3.	Is this problem discussed anywhere? if so, could you send
		us references?

One Dimensional Case:
	An optimal labeling with free boundary conditions is (obviously)
	1 2 3 4 5 6 7 8 9 ... (N-2) (N-1) N		MMD = 1

	With periodic boundary conditions, an optimal one is (for N even)
	1 3 5 7 9 ... (N-1) N (N-2) (N-4) ... 6 4 2     MMD = 2

This can be generalized to two and higher dimensions to get our upper bound
(left as an exercise to the reader).


			Dan Rokhsar
			Steve White