MAXIMAL SETS OF GIVEN DIAMETER IN THE GRID AND THE TORUS

The grid graph is the graph on [k]n = {0, 1, ..., k-1}n in which x=(x1 , ..., x(n)) is joined to y = (y1, ..., y(n)) if for some j we have \x (j) - y(j)\ = 1 and x(i) = y(i) for all i not-equal j. One of our aims in this paper is to determine, for each positive integer d, the maxim um size of a subset of [k]n of diameter d. The discrete torus is the c orresponding graph on Z(k)n = (Z/kZ)n: a point x=(x(i))1n is joined to y = (y(i))1n if for some j we have x(j) = y(j) +/- 1 and x(i) = y(i) for all i not-equal j. Our other main aim is to determine, for each d, the maximum size of a subset of Z(k)n of diameter d, in the case k ev en.