Maximal disarrangement of $n \times n$ numbers

2012-02-14T02:06:43Z

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}$:

Answer by Gjergji Zaimi for Maximal disarrangement of $n \times n$ numbers

2012-02-14T03:46:01Z

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.

Maximal disarrangement of $n \times n$ numbers - MathOverflow

Maximal disarrangement of $n \times n$ numbers

Answer by Gjergji Zaimi for Maximal disarrangement of $n \times n$ numbers