Maximal sets of given diameter in the grid and the torus (Q1313846): Difference between revisions

Let \([k]= \{0,1,\dots,k-1\}\). The grid graph \(G\) has vertices \(x= (x_ 1,\dots,x_ n)\), \(x_ i\in [k]\), with \(x\) joined to \(y\) precisely when there exists \(j\) such that \(| x_ j- y_ j|= 1\) and \(x_ i= y_ i\) for all \(i\neq j\). (Thus \(G\) is the product of \(n\) paths of order \(k\).) If \(A\subseteq [k]^ n\), define the diameter of \(A\) by \(\text{diam }A= \max\{d(x,y)\) : \(x,y\in A\}\), where \(d(x,y)\) is the graph distance. The problem of determining, for given \(k\), \(n\), \(d\), the maximal size of a subset of \([k]^ n\) of diameter \(d\) was discussed by \textit{D. J. Kleitman} and \textit{M. Fellows} [Discrete Math. 73, No. 1/2, 119-125 (1989; Zbl 0675.05001)]. The authors prove their conjecture that there is some \(c= (c_ 1,\dots,c_ n)\), \(c_ i\) not necessarily integers, such that the ball \(B\bigl(c, {1\over 2} d\bigr)\) has maximal size among sets of diameter \(d\). The authors also consider analogous problems for the discrete torus \((\mathbb{Z}/k\mathbb{Z})^ n\), obtaining the maximal size of a subset of diameter \(d\) in the case when \(k\) is even. They make use of some isoperimetric inequalities.