\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \newcommand{\odd}{\operatorname{odd}} \usepackage{epsf} \usepackage{subcaption} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf On the Maximum Number of Non-intersecting Diagonals in an Array \\ } \vskip 1cm \begin{minipage}[t]{0.45\textwidth} \begin{center} Peter Boyland\\ Department of Mathematical Sciences\\ Carnegie Mellon University\\ Pittsburgh, PA 15213 \\ USA\\ \href{mailto:pboyland@andrew.cmu.edu}{\tt pboyland@andrew.cmu.edu} \\ \ \\ Ivan Roth\\ Department of Mathematics, Statistics and Computer Science\\ Marquette University\\ Milwaukee, WI 53233 \\ USA \\ \href{mailto:ivan.roth@mu.edu}{\tt ivan.roth@mu.edu}\\[1ex] \end{center} \end{minipage} \begin{minipage}[t]{0.45\textwidth} \begin{center} Gabriella Pint\'er and Istv\'an Lauk\'o\\ Department of Mathematical Sciences\\ University of Wisconsin-Milwaukee\\ Milwaukee, WI 53211 \\ USA\\ \href{mailto:gapinter@uwm.edu}{\tt gapinter@uwm.edu}\\ \href{mailto:iglauko@uwm.edu}{\tt iglauko@uwm.edu} \\ \ \\ Jon E. Schoenfield\\ Huntsville, AL \\ USA \\ \href{mailto:jonscho@hiwaay.net}{\tt jonscho@hiwaay.net} \\ \end{center} \end{minipage} \bigskip Stephen Wasielewski\\ Rufus King International School --- High School\\ Milwaukee, WI 53209 \\ USA \\ \href{mailto:zeebaneighba21@gmail.com}{\tt zeebaneighba21@gmail.com} \end{center} \vskip .2 in \begin{abstract} We investigate the total number of diagonals that can be placed in the unit squares of a given grid in such a way that no two diagonals have a common point. We develop theoretical and computational results for square and rectangular shaped grids, and extend the problem to three-dimensional arrays. We pose some open questions for further investigation. \end{abstract} \section{Introduction} Constrained discrete planar or spatial filling problems are important in applications, and can lead to theoretically and computationally challenging questions. In this paper we consider an aspect of such a filling problem. Integer sequence \seqnum{A264041} in the OEIS \cite{OEIS} grew out of the following puzzle \cite{nrich}: \begin{quote} Sixteen unit squares are arranged in a square array. What is the maximum number of diagonals that can be drawn in these unit squares so that no two diagonals share a common point (including endpoints)? \end{quote} The problem is reminiscent of classical chessboard problems that involve placing the maximum number of certain types of chess pieces (e.g., queens, bishops, rooks or pawns) on the board so that no piece attacks another \cite{Gardner, Kot, pawns}. The number of possible arrangements containing the maximum number of pieces is often of interest as well. Typically, these kinds of problems can be cast in a graph theoretic setting, and computational techniques, for example, integer programming, can be very useful in obtaining some results. Our exposition follows the way the investigation of this problem unfolded. After some experimentation one can see that the maximum number of diagonals that can be placed in this particular grid according to the rules is $10$. The first question that arises naturally is the case of general $n \times n$ square arrays. In Section \ref{section_two} we study this problem and describe some partial results as well as upper and lower bounds for the maximum number of diagonals that can be placed in square arrays. In Section \ref{section_three} we extend the question to $m \times n$ rectangular arrays, and provide some theoretical and computational results together with some conjectures. In Section \ref{section_four} we describe our results for the three-dimensional case. We close by posing some open questions for further investigation. \section{Square arrays} \label{section_two} For $m,n \in \mathbb{Z}^{+}$, let $D(m,n)$ denote the maximum number of diagonals that can be placed in the unit squares of an $m \times n$ array so that no two diagonals cross or share an endpoint. We will use the notation $D(n)$ for $D(n,n)$. Some experimentation with $n=1,2,3,4$ yields $D(1)=1, \; D(2)=3,\; D(3)=6, \; D(4)=10$ (Figure \ref{fig:1}), which might lead to the conjecture that $D(n)=\frac{n(n+1)}{2}$. As we consider larger square arrays, however, we can see that the conjecture does not hold for $n=5$, since $D(5) \geq 16$. However, the arrangement (which we will refer to as the L-arrangement, since it places diagonals in cells that form nested L-shapes) seen in Figure \ref{fig:1} provides a lower bound for $D(n)$ for general $n \in \mathbb{Z}^+$. \begin{figure}[ht] \centering \begin{subfigure}[b]{0.20\textwidth} \centering \includegraphics[width=5mm]{fig1_1.eps} \caption{$D(1)=1$} \end{subfigure} \begin{subfigure}[b]{0.20\textwidth} \centering \includegraphics[width=10mm]{fig1_2.eps} \caption{$D(2)=3$} \end{subfigure} \begin{subfigure}[b]{0.25\textwidth} \centering \includegraphics[width=15mm]{fig1_3.eps} \caption{$D(3)=6$} \end{subfigure} \begin{subfigure}[b]{0.25\textwidth} \centering \includegraphics[width=20mm]{fig1_4.eps} \caption{$D(4)=10$} \end{subfigure} \caption{The first four square arrays.} \label{fig:1} \end{figure} \begin{proposition} For all $n \in \mathbb{Z}^+$, we have $D(n)\geq \frac{n(n+1)}{2}$. \label{lower_bd_sq} \end{proposition} \begin{proof} Note that the L-arrangement by which diagonals are placed in the square array in Figure \ref{fig:1} can always be realized. That is, `positive' (positive slope) diagonals can be drawn in the leftmost column and in the bottom row (forming the outermost L); then a column is skipped and diagonals are placed in the next column until we reach the $(n-2)$nd row, where the diagonals are continued to the right (forming the next L). The L-arrangement can also be done for rectangular arrays, and it will be used throughout the paper. The number of diagonals in the L-arrangement in a square array of side $n$ is $L(n)=L(n,n)=n+(n-1)+ \cdots +1= \frac{n(n+1)}{2}$, as can be seen by summing up the diagonals in the `legs' of the Ls. Thus, $L(n)\leq D(n)$. (We remark that another way to count the diagonals in this arrangement would be by considering the lattice points that are the endpoints of the diagonals (as described below), but the former method shows the connection to triangular numbers more transparently.) \end{proof} It turns out that in certain cases, for example, when $n$ is even, the L-arrangement provides not only a lower bound, but an upper bound as well. In particular, when the side of the square array is even, the corresponding triangular number is the answer to our original question. \begin{theorem} $D(2n)=L(2n)=n(2n+1)$, for all $n \in \mathbb{Z}^+$. \label{L-thm} \end{theorem} \begin{proof} From Proposition \ref{lower_bd_sq} we already know that $L(2n)\leq D(2n)$, so it suffices to show that $D(2n)\leq n(2n+1)=L(2n)$. Consider a $2n \times 2n$ array, and color the top horizontal line of lattice points red, the next one blue, the next one red, and so on, alternating these colors until the last (i.e., the $(2n+1)$st) horizontal line of lattice points, which will be red again as shown in Figure \ref{fig:colarg}. Any diagonal that is drawn in this array connects a red lattice point with a blue one. Since there are only $n(2n+1)$ blue lattice points and there can be at most one diagonal associated with any lattice point, we have $D(2n)\leq n(2n+1), $ which proves the claim. \end{proof} \begin{figure}[ht] \centering \includegraphics[height=1.5in]{Fig2_2_idea.eps} \caption{The coloring argument for even-sided squares. } \label{fig:colarg} \end{figure} The same argument shows the following result. \begin{proposition} For $m \in \mathbb{Z}^+$, any $m \times 2$ or $2 \times m$ segment of an array contains at most $m+1$ diagonals, and $D(2,m)=m+1$, for all $m \in \mathbb{Z}^+$. \label{cor1} \end{proposition} Theorem \ref{L-thm} provides an answer to our original question for square arrays with an even side, but as we have noted, squares of an odd side length may accommodate more diagonals than provided by the L-arrangement. We first consider a special case, $n=7$, and then develop a more general argument. \begin{proposition} $D(7)=29=L(7)+1$. \label{7-pr} \end{proposition} \begin{proof} Note that $L(7)=28$, so the claim is that the $7 \times 7$ square array can accommodate one extra diagonal above the L-arrangement. Let us divide the $7 \times 6$ array that results from omitting the leftmost column of the original square into three $7 \times 2$ pieces. Proposition \ref{cor1} implies that $D(7,6)\leq 3\cdot 8= 24$, so the maximum number of diagonals that can go into a $7 \times 7$ array satisfies $D(7)\leq 24+7=31$. Now let us assume that $D(7)\geq 30$. Since $D(7,6)=D(6,7) \leq 24$ this implies that columns 1 and 7 must each contain at least 6 diagonals, and so must rows 1 and 7. Since we also have that $D(2,7)=8$ (Proposition \ref{cor1} and L-arrangement), we can see that columns 2 and 6, as well as rows 2 and 6, contain at most 2 diagonals each. Now we repeat the argument for the $7 \times 5$ array that we get if we omit the first two columns of the original array. Since $D(7)\geq 30$ by assumption, this implies that $D(7,5) \geq 22$, and then since $D(7,4)\leq 2\cdot 8=16$, we can argue that at least 6 diagonals must fit in column 3 and column 5 of the original grid, and at most 2 diagonals can go in column 4. The same is true for the corresponding rows. Thus, each shaded column and row in Figure \ref{fig:2a} contains at most 2 diagonals, or a total of at most $3\cdot2+ 3\cdot2=12$ diagonals. Since there are only 16 non-shaded squares, the total number of diagonals that can be placed in the array would be at most 28, which is a contradiction; thus, $D(7)<30$. It is possible to place 29 diagonals in the $7 \times 7$ grid as shown in Figure \ref{fig:2b}. Hence, we can conclude that $D(7)=29=L(7)+1$. Note that a similar argument can be used to establish that $D(5)=16=L(5)+1$. \end{proof} \begin{figure}[h] \begin{subfigure}{0.45\textwidth} \centering \includegraphics[width=25mm]{fig2_ac.eps} \caption{Restrictions for $n=7$.} \label{fig:2a} \end{subfigure} \begin{subfigure}{0.45\textwidth} \centering \includegraphics[width=25mm]{fig1_7a_lb.eps} \caption{A solution with 29 diagonals for $n=7$.} \label{fig:2b} \end{subfigure} \caption{The $n=7$ case.} \label{fig:2} \end{figure} Since we can see that the number of diagonals can be larger than what is allowed by the L-arrangement in squares of odd sides, a natural question arises about how large this difference can be. Let us introduce the notation $K(n,m)=D(n,m)-L(n,m)$, where $K(n,m)$ is the number of extra diagonals accommodated by the array with dimensions $n$ and $m$ above the L-arrangement. The abbreviated notation $K(n)$ is used for $K(n,n)$. First we will show that $K$ is not bounded. \begin{proposition} $D(6m-1)\geq L(6m-1)+m$, that is, $K(6m-1)\geq m$. Thus, the number of extra diagonals above the L-arrangement is not bounded. \label{pr-6n} \end{proposition} \begin{proof} We prove the statement by an appropriate construction. Consider a $(6m-1) \times (6m-1)$ square, and put diagonals in its center $(2m+1) \times (2m+1)$ square in a checkerboard pattern starting with $m$ positive diagonals in its first row, and $(m+1)$ negative diagonals in its second one, alternating the number and orientation of the diagonals from row to row. See Figure \ref{fig:17constr} for the square of side $17$. \begin{figure}[h] \centering \begin{subfigure}[b]{0.5\textwidth} \centering \includegraphics[width=55mm]{fig3_17ba_lb.eps} \caption{Construction for $n=17$.} \label{fig:17constr} \end{subfigure} \begin{subfigure}[b]{0.4\textwidth} \centering \includegraphics[width=45mm]{fig3_11b_lb.eps} \caption{Construction for $n=13$.} \label{fig:13constr} \end{subfigure} \caption{The $n=17$ and $n=13$ cases.} \label{fig:13_17} \end{figure} Now consider the \emph{k}th diagonal from the left ($k=1,2, \dots ,m$) touching the top edge of the $(2m+1) \times (2m+1)$ center square. We place a positive diagonal in each of the $2k-1$ unit squares directly above this diagonal, then turn $90$ degrees counterclockwise, and continue placing positive diagonals until we reach the boundary of the $(6m-1) \times (6m-1)$ array. Next, we turn the entire $(6m-1) \times (6m-1)$ array $90$ degrees clockwise (or counterclockwise) and carry out the same procedure of placing diagonals using the new top edge. After two more repetitions, the construction is finished, as illustrated in Figure \ref{fig:17constr}. The construction results in the use of each of the $6m\cdot 6m$ lattice points of the $(6m-1) \times (6m-1)$ array as an endpoint of a diagonal, except for $4m$ lattice points along the sides of the array (marked by small yellow squares in Figure \ref{fig:17constr}). So the total number of diagonals placed is $\frac{6m\cdot 6m-4m}{2}=3m(6m-1)+m=L(6m-1)+m$, as claimed. \end{proof} Note that the construction above provides a lower bound for squares of sides $(6m+1)$ and $(6m+3)$ as well, since a full L-shape, i.e., $(6m+1)+6m$ diagonals, can be added in the width-2 `skirt' around the left and the bottom sides of a $(6m-1) \times (6m-1)$ square array. (Do this twice to fill a $(6m+3) \times (6m+3)$ array.) For a square of side $(6m+1)$ the construction results in $3m(6m-1)+m+(6m+1)+6m=(3m+1)(6m+1)+m=L(6m+1)+m$ diagonals, i.e., $D(6m+1)\geq L(6m+1)+m$. A similar calculation yields $D(6m+3)\geq L(6m+3)+m$. Upper bounds for $D$ in odd-sided squares can be established by generalizing the argument in Proposition \ref{7-pr} as follows. \begin{proposition} $D(2n+1)< L(2n+1)+M$, where $M=\left\lceil\frac{n(n+1)}{2n+1}\right\rceil = \left\lceil\frac{n+1}{2}\right\rceil, \; n\in \mathbb{Z}^+$. \label{odd_bd} \end{proposition} \begin{proof} We proceed by contradiction, and assume that $D(2n+1)\geq L(2n+1)+M$. Since there are at most $n(2n+2)$ diagonals in the $(2n+1) \times 2n$ array that we get by omitting the leftmost column, it follows that there must be at least $L(2n+1)+M-n(2n+2)=n+1+M$ diagonals in the first and last columns each (and in the first and last rows each). However, since there cannot be more than $(2n+2)$ diagonals total in the first two columns, there must be at most $n+1-M$ diagonals in the second column, and the $2n$th column, as well as in the second and $2n$th rows. The argument can be continued inside similarly as in the proof of Proposition \ref{7-pr} to obtain that each even-numbered column and row contains at most $n+1-M$ diagonals. This results in at most $2n(n+1-M)$ diagonals in these rows and columns, and $(n+1)^2$ open (non-shaded) squares that may admit diagonals; that is, a total of at most $2n(n+1-M)+(n+1)^2$ diagonals can be placed in the array. However, this is less than what we claim the array contains, and results in a contradiction, since $2n(n+1-M)+(n+1)^2\frac{n(n+1)}{2n+1}$. Note that $M \neq \frac{n(n+1)}{2n+1}$, since $\frac{n(n+1)}{2n+1}$ cannot be an integer if $n$ is a positive integer. In fact, we can see that $\left\lceil\frac{n(n+1)}{2n+1}\right\rceil=\left\lceil\frac{n+1}{2}\right\rceil $ since $\frac{n}{2}<\frac{n(n+1)}{2n+1}<\frac{n+1}{2}$, and this completes the proof of the proposition. \end{proof} We remark that the construction in Proposition \ref{pr-6n} together with the upper bound above can establish that $D(11)=68$. While the bound above is not sharp enough to determine $D$ for other odd values greater than $7$, we can combine it with our construction to determine that $1\leq K(9) \leq 2$, $2\leq K(13) \leq 3$, $2\leq K(15) \leq 3$, and in general, $\left\lfloor\frac{n+1}{3}\right\rfloor \leq K(2n+1) \leq \left\lfloor\frac{n}{2}\right\rfloor.$ The following bound is also useful. \begin{proposition} $K(2n+1) \leq K(2n-1)+1$. \end{proposition} \begin{proof} In general, we have that $D(2n+1)\leq D(2n-1)+D(2n+1,2)+D(2,2n-1)$. That is, \begin{eqnarray*} L(2n+1)+K(2n+1)&\leq& L(2n-1)+K(2n-1)+2n+2+2n\nonumber\\ (n+1)(2n+1)+K(2n+1)&\leq & n(2n-1)+K(2n-1)+4n+2\nonumber\\ K(2n+1)&\leq& K(2n-1)+1. \end{eqnarray*} \end{proof} \section{Rectangular arrays} \label{section_three} The diagonal placement problem can naturally be extended to rectangular arrays. In fact, we have already shown that $D(2,n)=n+1$ for all $n \in \mathbb{Z^+}$. However, before considering the general case, let us examine what happens to the L-arrangement in rectangular arrays. \begin{proposition} The number of diagonals in the L-arrangement in rectangular arrays is given by $L(2m+1,2n+1)=L(2n+1,2m+1)=(2m+1)(n+1)$ and $L(2m,2n)=L(2n,2m)=n(2m+1)$ for all $n \leq m,\, n,m \in \mathbb{Z^+}$, while $L(2m+1,2n)=L(2n,2m+1)=2n(m+1)$ for all $ n,m \in \mathbb{Z^+}$. Furthermore, when both dimensions of the rectangle are odd, $L(m,n)=L(n,m)=\max(m,n)(\min(m,n)+1)/2$. \end{proposition} \begin{proof} We can see that $L(m,n)$ can be expressed recursively, since the number of diagonals in the L-arrangement in the $m \times n$ rectangle is equal to the number of diagonals in the L-arrangement in the $(m-2) \times (n-2)$ rectangle plus the number of diagonals in the outermost L, that is, the number of cells along the left and bottom edges of the rectangle. Thus, $$L(m,n)=m+n-1+L(m-2,n-2),\;\; \text{for $m,n \geq 2$}$$ and $$ L(m,1)=m,\, L(1,n)=n, \, L(m,0)=0, \, L(0,n)=0.$$ For the case when both dimensions of the rectangle are odd, we have \begin{displaymath} L(2m+1,2n+1) = \begin{cases} (2m+1)+(2n+1)-1+L(2m-1,2n-1), & \text{for $m,n > 0$;}\\ 2m+1, & \text{for $n=0$;}\\ 2n+1, & \text{for $m=0$.} \end{cases} \end{displaymath} Now we can expand the above equation iteratively, assuming that $m\geq n$, as follows: \begin{eqnarray*} L(2m+1,2n+1)&=& (2m+1)+(2n+1)-1+L(2m-1,2n-1)\\ &=& (2m+2n+1) + ((2m-1)+(2n-1)-1) + L(2m-3,2n-3)\\ &\vdots & \\ &=& (2m+2n+1)+ (2m+2n-3) + \cdots + L(2m-2n+1,1)\\ &=& (2m+2n+1)+(2m+2n-3) + \cdots + (2m-2n+1)\\ &=& (2m+1)(n+1).\\ \end{eqnarray*} This proves the statement for the case when both dimensions of the rectangle are odd. Moreover, it is easy to see that $$L(2m+1,2n+1)=(2m+1)(n+1)=\max(2m+1,2n+1)(\min(2m+1,2n+1)+1)/2,$$ as claimed. The other cases, that is, when both sides of the rectangle are even, or when one is even and the other is odd, can be proved similarly based on the recursion for $L(m,n)$. \end{proof} Now, Theorem \ref{L-thm} can easily be generalized to cover all rectangular arrays with at least one even side. \begin{theorem} $D(2n, 2m+1)=L(2n,2m+1)=n(2m+2)$ for all $n,m \in \mathbb{Z^+}$ and $D(2n,2m)=L(2n,2m)=n(2m+1)$ for all $n \leq m$, $n,m \in \mathbb{Z^+}$. \label{even_side} \end{theorem} \begin{proof} First consider a $2n \times (2m+1)$ array. Color the lattice points on the top horizontal gridline red. Make the next line of lattice points blue and continue alternating the color of the lattice points line by line, until the last horizontal line, where the lattice points are red again since the array has an even number of rows. Thus we obtain $n+1$ red and $n$ blue lines of lattice points. Since every diagonal connects a red and a blue lattice point, it follows that $D(2n, 2m+1) \leq n(2m+2)$. The L-arrangement in the array provides exactly $(m+1)\cdot 2n=n(2m+2)$ diagonals, as can be seen by adding the number of diagonals in pairs of rows. Thus we can conclude that $D(2n, 2m+1)=n(2m+2)$. The case when both sides are even is very similar. Here we have $D(2n,2m)\leq n(2m+1)$ and $D(2n,2m)\leq m(2n+1)$ by applying the coloring argument along both dimensions. Since $n \leq m$ by assumption, $D(2n,2m)\leq n(2m+1)$ is the sharper bound, and the L-arrangement makes the placement of this many diagonals in the array possible. Thus $D(2n,2m)=n(2m+1)$ when $n \leq m$. \end{proof} As was the case with square arrays, we can see that only rectangles with both dimensions odd have the potential to accommodate more diagonals than what the L-arrangement would provide, and these are the interesting cases to investigate. Some experimentation suggests that $D(7,5)=L(7,5)=21$, but $D(9,7)=L(9,7)+1=37, $ while $D(11,7)=L(11,7)$. That is, we can no longer do better than the L-arrangement once the array becomes sufficiently oblong. To examine this and the square case systematically, we turned to computational algorithms that implemented an exhaustive search to find $D(n,m)$ in general, together with the number of solutions containing the maximum number of diagonals for a given array size. \subsection{Search algorithms} As described by Israel in a comment for sequence \seqnum{A264041} in the OEIS \cite{OEIS}, the diagonal problem can be cast as that of finding a maximum independent set in an appropriate graph $G$. Let the vertices of $G$ correspond to the diagonals in an $n \times m$ array and be indexed by the triple $(x,y,z)$, where $1\leq x \leq n$, $1\leq y \leq m$, and $z=1,2$, with $z=1$ corresponding to `positive' diagonals (positive slope) and $z=2$ corresponding to `negative' diagonals (negative slope). Two vertices are connected by an edge in $G$ whenever the two corresponding diagonals have a common point. Thus $(x,y,1)$ is connected to $(x,y,2)$ for every $1\leq x \leq n$, $1\leq y \leq m$. Additionally, $(x,y,1)$ is connected to $(x+1,y+1,1)$, $(x,y,2)$ to $(x+1,y-1,2)$, and $(x,y,z)$ is connected to both $(x+1,y,3-z)$ and $(x,y+1,3-z)$. The search for a maximum independent set in $G$ was performed using integer programming by means of an IBM ILOG CPLEX \cite{ibm} routine in MATLAB. The code by Israel that treats square arrays is available through a link under sequence \seqnum{A264041} in the OEIS \cite{OEIS}. We adapted the code to cover rectangular arrays, and ran it until computer memory and/or run time limited the size of arrays that could be solved this way as described under \seqnum{A260690} in the OEIS \cite{OEIS}. Our computational results for arrays of odd dimensions are summarized in Figure \ref{fig:compres}. One can readily observe how the more oblong arrays lose the potential of accommodating extra diagonals above the L-arrangement. \begin{figure}[H] \centering \includegraphics[width=6in]{Fig_5_retrofit_latex_try_edit1_uj3n.eps} \caption{Computed values of $D(n,m)$. Values in cells without all four borders and with numbers in small font are conjectures; other values are verified maxima for the given dimensions. Colors indicate the number of extra diagonals that the array can accommodate above the L-arrangement.} \label{fig:compres} \end{figure} We remark that a more direct search algorithm has also been developed by one of the authors (Schoenfield) that fills the array row by row, and counts the number of optimal solutions for each pair $(n,m)$ where both $n$ and $m$ are odd. Table \ref{numsol} gives the number of arrangements that have the maximum number of diagonals for an $n \times m $ array. \begin{table}[H] \centering \begin{tabular}{|c||c|c|c|c|c|c|c|c|} \hline & \textbf{1} & \textbf{3} & \textbf{5} & \textbf{7} & \textbf{9} & \textbf{11} &\textbf{13} &\textbf{15} \\\hline\hline \textbf{1} & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2\\ \textbf{3} & 2 & 28 & 30 & 34 & 38 & 42 &46 & 50\\ \textbf{5} & 2& 30& 2 & 2482 & 3266 &4210 &5282 &6482\\ \textbf{7} & 2 & 34 & 2482 & 480 & 32 & 1634780 & 2555996&3832876\\ \textbf{9} & 2 & 38 & 3266 & 32 & 433284 & 85328 & 7568 & 256\\ \textbf{11} & 2& 42 & 4210 & 1634780 & 85328 & 256 & 619672582& 133534888\\ \textbf{13} & 2& 46 &5282 &2555996 &7568 & 619672582 &14454384 & 28224\\ \textbf{15} & 2 & 50 & 6482& 3832876 & 256& 133534888 & 28224& 1401615406696\\ \hline \end{tabular} \caption{Number of optimal solutions for rectangular arrays. Arrangements that can be rotated and/or reflected into each other are counted as distinct.}\label{numsol} \end{table} \begin{figure}[h] \centering \includegraphics[height=4in]{h_11_w_011_solns_vis_large_lb6.eps} \caption{Some computed solutions for the $11 \times 11$ array. Instead of showing each diagonal, cells that have a positive diagonal are colored red, while cells with a negative diagonal are blue.} \label{fig:11sols} \end{figure} Some of the $256$ solutions for the $11 \times 11$ array are depicted in Figure \ref{fig:11sols}. While visualizing the computed arrangements, one can observe that some of them seem to be forming `braids' through the array. This is even more noticeable if the cells containing positive diagonals are painted in one color, and negative diagonals in another color. In fact, these braids can provide a convenient way of constructing solutions with $K(n,m)>0$ for certain types of rectangular arrays. \begin{figure}[h] \centering \includegraphics[height=4in]{Fig7_blue_76_76_255_cropped} \caption{A braided solution for a $ 21 \times 11$ array. Arrows show the entry and exit points of the red (positive diagonals) and blue (negative diagonals) threads.} \label{fig:braidex} \end{figure} \subsection{Braided solutions} \label{sec_braids} Let us consider the $21 \times 11$ braid pattern in Figure \ref{fig:braidex}. It has $L(21,11)+1=126+1=127$ diagonals, that is, it admits the maximal one extra diagonal above the L-arrangement since we know that $D(21,11)=127$ (see Figure \ref{fig:compres}). It is achieved in the following way. In each pair of rows there can be at most 12 diagonals, and here we have 7 diagonals in each odd row, and 5 in each even one. Thus, the last row, which is an odd row, will contain 7 diagonals, which is one more than the average of 6 per row, which comes from the L-arrangement: $L(21,11)=6 \cdot 21$ (which is the same total number of diagonals as would be obtained from simply having 6 vertical threads, one filling each odd-numbered column). The extra diagonal in each odd row is created by `sliding' the threads horizontally. We can devise a general strategy of constructing braid patterns along these lines, and we can examine how many extra diagonals they admit. Let $w,h$ be both odd, with $w$ denoting the number of columns, and $h$ the number of rows in a particular array. Suppose we attempt to construct a braided solution with $K$ extra diagonals (where $K\geq 1$ is a given value) in which the number of diagonals in every odd-numbered row is $\frac{w+1}{2} + K$, and the number of diagonals in every even-numbered row is $\frac{w+1}{2} - K$. We do not place a diagonal in any cell that is the intersection of an even-numbered row and an even-numbered column. The diagonals lie along $\frac{w+1}{2} - K$ braided threads, with each thread occupying exactly one cell on each even-numbered row. However, collectively, the threads occupy an additional $2K$ cells on each odd-numbered row. If we envision a `zeroth row' just above the top of the grid, there are `entry points' (at odd-numbered columns) for each of the red (positive diagonals) threads starting from the left, and for the blue (negative diagonals) threads starting from the right, with K entry points in between that are left empty. Constructing the pattern from the top row downward, each thread's contribution to these $2K$ additional cells is accomplished by `sliding' to the left (for blue threads) or right (for red threads) by an even number of columns, sometimes jumping across one or more threads of the opposite color. Consider only the $C = \frac{w+1}{2}$ odd columns, and start from the left with $R$ entry points for the $R$ red threads, followed by $K$ empty entry points, followed by $B$ entry points for the $B$ blue threads: $R + K + B = C$. No thread crosses any thread of the same color, but since the blue threads will end up on the left and the red threads on the right, every thread crosses every thread of the opposite color. Below the bottom row, picture an $(h+1)$st row for `exit points'. There will be $B$ exit points for the blue threads, $K$ empty exit points, and $R$ exit points for the red threads. Between the entry row $(0)$ and the exit row $(h+1)$, each red thread will have been slid to the right by at most $K+B$ odd columns, and each blue thread will have been slid to the left by at most $K+R$ odd columns. Each `slide' covers an additional $2J$ diagonals where $J$ is the length of the slide, in odd columns. However, each crossing of threads deducts two diagonals, i.e., it does not gain one for the color being slid, and it does remove one of the opposite color. The maximum number of `additional' diagonals, that is, `additional' beyond the $(R+B)\cdot h$ diagonals that would be drawn if each thread were simply drawn as a single, vertical column, is $2R \cdot(K+B)+2B\cdot (K+R)- 2RB$, in which the terms $2R \cdot(K+B)$, $2B\cdot (K+R)$ and $- 2RB$ account for the additional diagonals from sliding the reds to the right, those from sliding the blues to the left, and the diagonals lost because of the thread crossings, respectively. To maintain the alternating number of diagonals per row as $\frac{w+1}{2} + K$ on each odd-numbered row and $\frac{w+1}{2} - K$ on each even-numbered row, we must get $2K$ extra diagonals on each odd-numbered row. This can be maintained for a maximum of $$h_{\odd,\max} = \left\lfloor\frac{2R\cdot (K+B) + 2B\cdot(K+R) - 2RB} {2K}\right\rfloor =R+B+\left\lfloor\frac{RB}{K}\right\rfloor$$ odd-numbered rows, which potentially allows construction of a pattern whose height is at most $h_{\max}=2\cdot h_{\odd,\max} - 1$ rows. The quantity $R+B+\lfloor\frac{RB}{K}\rfloor$ is maximized if $R$ and $B$ are as nearly equal as possible (since their sum is fixed). Thus we can arbitrarily set $B = \lfloor\frac{C-K}{2}\rfloor$ and then let $R = C - K - B$. The resulting $h_{\max} \times w$ array would have $K$ extra diagonals above $L(h_{\max}, w)$, that is, $T(h_{\max},w)=L(h_{\max}, w)+K$, where $T(h,w)$ denotes the number of diagonals that can be placed in an $h \times w$ array using the braid construction described above. Thus, $D(h_{\max},w) \geq T(h_{\max},w)$, which provides a sharper lower bound than the one from the L-arrangement. In our former example with $w=11$, the argument would go the following way. The question is what the largest $h\geq w$ is such that $K(h,w)=1$. Then $C=6=R+B+1$, so we can let $R=3,\; B=2$, i.e., have three red and two blue threads. The construction described above can potentially be maintained for $h_{\odd,\max}=5+6=11$ odd rows, or $h_{\max}=21$ rows, so it would result in a $21 \times 11$ array with 1 extra diagonal above the L-arrangement. Thus $T(21,11)=127$, which turns out to be the same as $D(21,11)$. Figure \ref{fig:braidex} shows the construction, so we can see that it is feasible in this case. Note that this result also provides the lower bound $D(h,11)\geq T(h,11)\geq L(h,11)+1$ for $h_{\max}=21 \geq h\geq 11$, $h$ odd. Now take $K=2$. In this case, $R+B=4$, so let $R=B=2$. We can see that $h_{\max}=11$, which could lead to any of the arrangements in the last column of Figure \ref{fig:11sols}. If one takes $K=3$, then $R+B=3$, and $h_{\max}= 5$, which is smaller than $w=11$. So a braided solution with 3 extra diagonals is not possible in arrays with 11 columns. While this argument is very appealing, and the construction seems straightforward as shown in Figure \ref{fig:braidex}, one might run into difficulties, especially when there are many empty entry/exit points. Thus it is important to investigate whether this construction could actually be carried out for all relevant values of $R,B$ and $K$. \subsection{Feasibility of the braid construction} Our first observation concerns a potential reduction in the number of red or blue threads. \begin{proposition} Suppose $w$ and $h$ are odd, $w\leq h$. Let $R+B+K= \frac{w+1}{2}$, $R\geq K$, and assume that the goal is to construct a braided solution for $(K,R,B)$. This problem can be reduced to that of finding a braided solution for $(K, R-K,B)$. Similarly, any problem $(K,R,B)$ with $B\geq K$ can be reduced to $(K,R,B-K)$. \end{proposition} \begin{proof} If $R\geq K$, the problem of finding a braided solution for $(K,R,B)$ can be simply reduced to the problem of finding a braided solution for $(K, R-K, B)$ by making the following moves (i.e., horizontal slides of the threads) on successive odd rows (beginning with row 1): \begin{itemize} \item[1.] For each of the first $B$ moves, move the leftmost movable blue thread as far as possible to the left. \item[2.] For each of the next $K$ moves, move the rightmost movable red thread as far as possible to the right (jumping over all the blue threads). \end{itemize} After these moves, $K$ of the red threads are in their final positions occupying the $K$ rightmost odd columns of the array, so the problem is reduced to that of finding a set of moves that will successfully solve the remaining problem that has only $R-K$ red threads at the far left, followed by $K$ empty columns, followed by the $B$ blue threads on the right. The reduction of the number of blue threads can be done similarly, with red and blue as well as left and right interchanged. \end{proof} We remark that the reduction steps described above can be applied several times, one after another. Thus, we can state the following corollary. \begin{corollary} The problem of finding a braided solution for $(K,R,B)$ reduces to that of $(K, R', B')=(K,R\bmod K,B\bmod K)$. \end{corollary} In the following, let $R'= R\bmod K$ and $B'=B\bmod K$. We note that braided solutions for $(K,0,B'), $ or for $(K,R',0)$, are very easy to construct. In each case the blue (or red) threads can simply slide $K$ odd columns one after the other to the left (or to the right) in consecutive odd rows until they reach their end positions. A rectangular array with $w=(6n+1)$ columns and $K=n$ leads to finding a braided solution for $(n,n+1,n)$, which reduces to $(n,1,0)$, while arrays with $w=(6n+3)$ columns and $K=n$ lead to $(n,n+1,n+1)$, which reduces to $(n,1,1)$. In general, any $(K, R', B')$ problem with $B' = 1$ can be solved in the following way. \begin{itemize} \item[1.] For the first move, move the blue thread as far as possible to the left. \item[2.] For each of the next $R'$ moves, move the rightmost movable red thread as far as possible to the right (jumping over the blue thread). \end{itemize} Of course, the steps above work with red and blue (and left and right) interchanged as well, reflecting the symmetry of the problem. \begin{example} Consider $w=29$ and suppose we are looking for arrays with $K=4$ extra diagonals. According to the formulas in Section \ref{sec_braids} for $h_{\odd,\max}$ and $h_{\max}$, the largest 29-column array for which a braided solution can accommodate four extra diagonals has $h_{\max}=2(11+\lfloor\frac{30}{4}\rfloor)-1=35$ rows. Thus we look for a braided solution for $(4,6,5)$, which we can reduce to $(4,2,5)$, then to $(4,2,1)$. The relevant steps are illustrated in Figure \ref{fig:redconst}. \begin{figure}[ht] \centering \includegraphics[height=4in]{figbraid_29a_lb.eps} \caption{A braided solution for a $ 35 \times 29$ array. The first reduction yields the reduced solution in the yellow box, while the second yields the one in the black box. } \label{fig:redconst} \end{figure} \end{example} It is also possible to devise a construction pattern for the general case $(K,R',2), $ or $(K,2,B')$, but it may be much more complicated for some values of $K$ and $R'$ or of $K$ and $B'$. We have tested a general algorithm that, while considerably more complex than the ones described above, successfully generates a braided solution with $h_{\max}=2(R'+B'+\lfloor \frac{R'B'}{K}\rfloor)-1$ rows for all cases where $R'=\lceil \frac{R'+B'}{2} \rceil$ and $R'