Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
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

1 Answer 1

up vote 13 down vote accepted

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.

share|improve this answer
    
Brilliant! $\mbox{}$ –  Joseph O'Rourke Feb 14 '12 at 12:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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