# Maximal disarrangement of $n \times n$ numbers

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}$: • 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 – Gerhard Paseman Feb 14 '12 at 2:34
• 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 – Gerhard Paseman Feb 14 '12 at 2:39
• I added the graph-theory tag, since this is a well-known problem in that area. – Gjergji Zaimi Feb 14 '12 at 3:48

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.
• Brilliant! $\mbox{}$ – Joseph O'Rourke Feb 14 '12 at 12:16