Maximal disarrangement of $n \times n$ numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T14:16:22Z http://mathoverflow.net/feeds/question/88393 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88393/maximal-disarrangement-of-n-times-n-numbers Maximal disarrangement of $n \times n$ numbers Joseph O'Rourke 2012-02-14T02:06:43Z 2012-02-14T11:42:47Z <p>This question is inspired by Martin Erickson's question, "<a href="http://mathoverflow.net/questions/88346/" rel="nofollow">Labeling a Square Array</a>." I'll start by quoting Martin:</p> <blockquote> <p>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$.</p> </blockquote> <p>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$?</p> <p>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...</p> <p><em>Examples</em>. For $n=2$, $\delta=1$, e.g., <code>$$\left( \begin{array}{cc} 3&amp;2\\ 1&amp;4 \\ \end{array} \right) \;.$$</code> For $n=3$, $\delta=3$, e.g., <code>$$\left( \begin{array}{ccc} 1&amp;4&amp;7\\ 5&amp;8&amp;2 \\ 9&amp;3&amp;6 \end{array} \right) \;.$$</code></p> <p><b>Addendum</b>. Here is an illustration of Gjergji Zaimi's solution, achieving, for $n=5$, $\delta=10=\binom{5}{2}$: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/SquareDerrangement.jpg" alt="Derrangement" /></p> http://mathoverflow.net/questions/88393/maximal-disarrangement-of-n-times-n-numbers/88397#88397 Answer by Gjergji Zaimi for Maximal disarrangement of $n \times n$ numbers Gjergji Zaimi 2012-02-14T03:46:01Z 2012-02-14T03:46:01Z <p>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 <em>separation number</em> of a graph. Some recent papers call this the antibandwidth problem.</p> <p>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.</p> <p>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.</p>