7
$\begingroup$

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin:

the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, n^2$. Under the traditional left-to-right and top-to-bottom labeling, the labels of horizontally adjacent cells differ by $1$, and the labels of vertically adjacent cells differ by $n$.

Let $\delta$ be the minimum absolute label difference between any cells adjacent horizontally or vertically in a particular filling of the array by those $n^2$ numbers. So $\delta=1$ in the standard filling. What is the maximum of $\delta$ as a function of $n$?

In a sense, this is asking for a maximal "disarrangement" of the $n^2$ numbers. Phrased that way, it sounds like it may have applications and therefore be well-studied: perhaps in the discrepancy theory literature? Or perhaps it is entirely elementary...

Examples. For $n=2$, $\delta=1$, e.g., $$ \left( \begin{array}{cc} 3&2\\ 1&4 \\ \end{array} \right) \;. $$ For $n=3$, $\delta=3$, e.g., $$ \left( \begin{array}{ccc} 1&4&7\\ 5&8&2 \\ 9&3&6 \end{array} \right) \;. $$

Addendum. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$:


               

$\endgroup$
3
  • 1
    $\begingroup$ For large even n, one should get close to N=n^2/4 by using 2x2 tiles having j, j+N, j+2N, j+3N, for ascending values of j. I think a pigeonhole argument will show N is optimal, but I do not have a proof yet. Gerhard "Ask Me About System Design" Paseman, 2012.02.13 $\endgroup$ Feb 14, 2012 at 2:34
  • $\begingroup$ I have a sense that the d-dimensional version will have (n/2)^d as the limit for the minimum. Perhaps fedja or Gjergji can favor us with a proof or refutation? Gerhard "Ask Me About System Design" Paseman, 2012.02.13 $\endgroup$ Feb 14, 2012 at 2:39
  • $\begingroup$ I added the graph-theory tag, since this is a well-known problem in that area. $\endgroup$ Feb 14, 2012 at 3:48

1 Answer 1

15
$\begingroup$

The problem of minimizing the maximum difference of adjacent values in a labelled graph is called "bandwidth minimization". Recently there was interest in the dual problem of maximizing the minimum such difference, and it was originally called the separation number of a graph. Some recent papers call this the antibandwidth problem.

You are interested in the antibandwidth number for $P_n\times P_n$, where $P_n$ denotes the path of length $n$. Recently the antibandwidth problem was solved for all meshes and similar toroidal graphs. See "Antibandwidth and Cyclic Antibandwidth of Meshes and Hypercubes" by A. Raspaud, H. Schroder, O. Sykora, L. Torok, and I. Vrto.

The answer is that the antibandwidth number of $P_n\times P_m$, $m\geq n$ is $$\lceil \frac{n(m-1)}{2}\rceil.$$ In particular the answer to your question is $\binom{n}{2}$. To see one construction which achieves this bound, simply color the squares in a chessboard fashion and then do a traditional labelling on the white squares first, and the black squares second.

$\endgroup$
1
  • $\begingroup$ Brilliant! $\mbox{}$ $\endgroup$ Feb 14, 2012 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.