\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<L(2n+1)+M=(n+1)(2n+1)+M$ by the fact that $M>\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'<K \leq 1000$. However, even the partial results here can provide more
insight into the structure of Figure \ref{fig:compres}. In particular, we note that the maximum number of diagonals in an array with odd dimensions agrees with
what the braid construction would provide for all computed values of $D(h,w)$. Thus, we conjecture that $T(h,w)=D(h,w)$ for $h,w$ odd.
Moreover, we claim the following.

\begin{proposition}
Suppose $w$ and $h$ are odd. The maximum number of diagonals that can be placed in the $h \times w$ array using a braided solution is $T(h,w)=L(h,w)+K$,
where $$K=\left\lfloor\frac{t-2s +2 \sqrt{t^2-st+s^2}}{3}\right\rfloor,$$ with $s=\frac{\max{(h,w)}+1}{2}$ and $t=\frac{\min{(h,w)}+1}{2}$.
\label{formula}
\end{proposition}

\begin{proof}
Assume that $h\geq w$, so $s=\frac{\max(h,w)+1}{2}=\frac{h+1}{2}$ and $t=\frac{\min(h,w)+1}{2}=\frac{w+1}{2}$. From the braided solution we have that
 $h_{\odd,\max}= \max\left(R+B+\lfloor\frac{RB}{K}\rfloor\right)$, where $R+B+K=t$. Thus  for fixed $w$ and $K$ $$h_{\max}(w,K)=2 h_{\odd,\max} -1=
    2\left( t-K+\left\lfloor \frac{\left( \frac{t-K}{2}\right)^2}{K}\right\rfloor \right) -1.$$ This means that if the $h \times w$ array
    has $K$ extra diagonals, then
    $$w\leq h\leq 2\left( t-K+\left\lfloor \frac{\left( \frac{t-K}{2}\right)^2}{K}\right\rfloor \right) -1,$$
    and we can solve this inequality for $K$.
    We obtain
    \begin{eqnarray*}
    \frac{h+1}{2}&\leq & t-K+\left\lfloor  \frac{\left( \frac{t-K}{2}\right) ^2}{K}\right\rfloor \\[1ex]
     \frac{h+1}{2}&\leq & t-K+\left\lfloor \frac{t^2-2tK+K^2}{K}\cdot \frac{1}{4}\right\rfloor\\[1ex]
     \frac{h+1}{2}&\leq & \left\lfloor \frac{4tK-4K^2+t^2-2tK+K^2}{4K} \right\rfloor\\[1ex]
     \frac{h+1}{2}&\leq & \left\lfloor \frac{t^2+2tK-3K^2}{4K} \right\rfloor.\\[1ex]
     \end{eqnarray*}
     Since $h$ is an odd integer, this is equivalent to
     \begin{eqnarray*}
     s=\frac{h+1}{2}&\leq & \frac{t^2+2tK-3K^2}{4K} \\[1ex]
     4sK &\leq & t^2+2tK-3K^2\\[1ex]
     0 &\leq & -3K^2+K(2t-4s) +t^2.\\[1ex]
    \end{eqnarray*}

    If we solve the quadratic equation $-3K^2+K(2t-4s) +t^2=0$ for $K, $ then we get
    $$K_{1,2}=\frac{4s-2t\pm \sqrt{(2t-4s)^2-4\cdot(-3)\cdot t^2}}{-6}=\frac{t-2s\mp 2 \sqrt{t^2-st+s^2}}{3}.$$ The solution of the quadratic inequality in turn
    is $$0\leq K\leq \frac{t-2s+2\sqrt{t^2-st+s^2}}{3},$$ since $K\geq 0$. Thus the $h \times w$ array can accommodate at least $K$ extra diagonals by the braid construction
    whenever $K$ satisfies the inequality above. Moreover, the largest such $K, $ i.e., $$K=\left\lfloor\frac{t-2s +2 \sqrt{t^2-st+s^2}}{3}\right\rfloor,$$ is the
    one that provides $T(h,w)=L(h,w)+K$.
\end{proof}



\section{Three-dimensional arrays}
\label{section_four}
The original problem can be naturally generalized to three-dimensional arrays. Instead of diagonals in unit squares, consider the space diagonals in the unit cubes that
make up the array, and require that no two of the space diagonals placed in the unit cubes of the array cross or share an endpoint. While the straightforward generalization
of the coloring argument to parallel planes of lattice points fails, it can be modified to provide a very useful upper bound.

\begin{proposition}
The maximum number of space diagonals in a $2n \times 2m \times 2k, \; n\leq m \leq k$ array is
\begin{displaymath}
   D(2n,2m,2k) \leq
     \begin{cases}
       4nmk+nm+nk+mk, & \text{if $n(m+1) \geq (m-n)k$;}\\
       4nmk+ n(2m+2k+1), &  \text{otherwise.}
     \end{cases}
\end{displaymath}
\label{3dupbd}
\end{proposition}
\begin{proof}
Let us label the lattice points in the array with 0s and 1s alternating in each direction, $x,y,z$, starting with 0. That is, each lattice point will be assigned
a triple $(a,b,c)= (x \bmod 2, y \bmod 2, z \bmod 2)$. The crucial observation is that each space diagonal connects a lattice point labeled $(a,b,c)$ with one labeled $(1-a,1-b,1-c)$. Table \ref{table2} lists the number of different types of lattice points
in the array.

\vspace{0.5cm}

\begin{table}[h]
\centering
\begin{tabular}{|c|c||c|c|}
  \hline
  \textbf{lattice point} & \textbf{number} & \textbf{lattice point type} & \textbf{number} \\
  \textbf{type}          &  \textbf{of points} & \textbf{connected to} & \textbf{of points} \\ \hline
  $(0,0,0)$ & $(n+1)(m+1)(k+1)$ & $(1,1,1)$ & $nmk$ \\
  $(0,0,1)$ & $(n+1)(m+1)k$ & $(1,1,0)$ & $nm(k+1)$ \\
  $(0,1,0)$ & $(n+1)m(k+1)$ & $(1,0,1)$ & $n(m+1)k$ \\
  $(1,0,0)$ & $n(m+1)(k+1)$ & $(0,1,1)$ & $(n+1)mk$ \\
  \hline
\end{tabular}
\caption{The number of different types of lattice points in a $2n \times 2m \times 2k, \; n\leq m \leq k$ array.}
\label{table2}
\end{table}


\noindent For example, we can see that there can be at most $nmk$ space diagonals that connect lattice points of types $(0,0,0)$ and $(1,1,1)$. As we continue this way, and take the
minimum number of diagonals in each row of the table, we arrive at the upper bound

\begin{eqnarray*}
D(2n,2m,2k) \leq & & \min{((n+1)(m+1)(k+1),nmk)}\\
&+& \min{((n+1)(m+1)k,nm(k+1))}\\
&+& \min{((n+1)m(k+1),n(m+1)k)}\\
&+& \min{(n(m+1)(k+1),(n+1)mk)}\\
=& & nmk+nm(k+1)+n(m+1)k\\
&+&\min{(n(m+1)(k+1),(n+1)mk)},
\end{eqnarray*}
which implies the claim.
\end{proof}

One of the first interesting three-dimensional arrays is the $2 \times 2 \times 2$ cube. It is not necessarily easy to see directly that there cannot be 8 non-intersecting space
diagonals in this array, but we can use Proposition \ref{3dupbd} to establish that $D(2,2,2) \leq 7$. However, 7 diagonals can be placed in this array, so $D(2,2,2)=7$.
Figure \ref{fig:222} illustrates one way of placing 7 diagonals in the array. From the bottom ($0$th) level, four space diagonals are drawn upward, each in the same direction. Then from
level 1, three more diagonals, also extending upward, can fit in an L-shape. In fact, it turns out that the upper bound above and the type of construction here combine to determine $D$ for all
even-sided cubes, and for tall rectangular prisms with a square base (tall square columns) with all sides even.



\begin{figure}[H]
  \centering
    \includegraphics[width=0.8in]{fig3d222_2alev_n.eps}
\caption{Seven space diagonals in a $2 \times 2 \times 2$ cube. Circles denote the lower endpoint of a diagonal at level $i$, while their upper endpoint at level $i+1$ is marked by an x.  }
    \label{fig:222}
\end{figure}



\begin{proposition}
For a $2n \times 2n \times 2k$ array with $k\geq n$, $D(2n,2n,2k)=4n^2k\,+\,n^2\,+\,2nk$.
\end{proposition}

\begin{proof}
First, by Proposition \ref{3dupbd} we have that $D(2n,2n,2k)\leq 4n^2k+n^2+2nk$. Next, we demonstrate a general construction that places exactly $4n^2k+n^2+2nk$ space diagonals
in the $2n \times 2n \times 2k$ array by expanding on the example above. At the bottom of the column, level 0, we can place $(2n)^2$ space diagonals, all going the
 same way. This will leave all
lattice points along two intersecting sides of the next level in the prism free (i.e., no diagonals connect to them from below). Thus, space diagonals
originating at these points can be placed in level 1, again in the same orientation as those
in level 0. This results in $4n-1$ diagonals in an L-shape. In level 2, not only can we again place the same type of diagonals in the L-shape as one level below, but we
can start diagonals from $(2n-2)^2$ lattice points `inside' the L-shape as well. In level 3, we can repeat the large L, but not the square inside, rather, just
the L-shaped boundary of the square nesting into the larger L. As we proceed upwards, the levels with nested Ls and a square alternate with just nested Ls (but one
more than before) until there is no more room for more L-shapes in level $2n$. From that point on, each level can repeat the full nested-L pattern.
\vspace{0.5cm}

\begin{figure}[H]
  \centering
    \includegraphics[height=4in]{fig3d444_4alev_n.eps}
\caption{44 diagonals in a $4 \times 4 \times 4$ cube.}
    \label{fig:444}
\end{figure}

If we sum up the number of diagonals
in pairs of levels from the bottom up, we obtain
\begin{eqnarray*}
&&[4n^2+(4n-1)]+[(4n-1+(2n-2)^2) +(4n-1+4n-5)]\\
&&\;\;\;+[(4n-1+4n-5+(2n-4)^2)+(4n-1+4n-5+4n-9)] \\
&&\;\;\;+\cdots+ (k-n)[2n(2n+1)]\\
&&=[4n^2+(4n-1)]+[4n^2+(4n-3)]+ [4n^2+(4n-5)]+\cdots \\
&&\;\;\;+ [4n^2+(4n-(2n-1))]+(k-n)[2n(2n+1)]\\
 &&= 4n^3+3n^2+ (k-n)[2n(2n+1)]\\
 &&= 4n^2k+n^2+2nk.
 \end{eqnarray*}
 This arrangement can also be thought of as a collection of nested shells with one horizontal and two vertical adjacent sides.
 \end{proof}
 We remark that this construction can be considered as a type of generalization of the L-arrangement from the two-dimensional problem, and we just showed that it places the maximum possible number of diagonals in tall even-sided prisms with a square base. The arrangement itself does not depend on the parity of the sides of the array. We will refer to this construction as the `nested-shell arrangement' below, and denote the number of diagonals it places into an $n \times m \times k$ array by $S(n,m,k)$.

 \begin{proposition}
 The number of diagonals in the nested-shell arrangement described above is given by
 \begin{displaymath}
   S(n,m,k) =
     \begin{cases}
       \frac{1}{4}n(2mk+2m+2k-n),&  \text{for $n$ even;}\\[2ex]
       \frac{1}{4}(n+1)(2mk+n-1),&   \text{for $n$ odd.}
     \end{cases}
\end{displaymath}
where $0\leq n\leq m \leq k$.
 \end{proposition}

\begin{proof}
The proof is very similar to the one we had for the L-arrangement in the two-dimensional case. First, we note that $S(0,m,k)=0$ for all $m,k \geq 0$, and $S(1,m,k)=mk$, for all $m,k \geq 1$, so the formulae work for $n=0$ and $n=1$. Next, we can see from the construction of the nested shells that the outermost shell contains $nm+nk+mk-n-m-k+1$ diagonals. Thus $S$ satisfies the following recursion for $2 \leq n \leq m \leq k$:
$$ S(n,m,k)=nm+nk+mk-n-m-k+1+S(n-2,m-2,k-2).$$
Now, if we assume that $n$ is even and iteratively expand the terms using the recursion above, we obtain
\begin{eqnarray*}
S(n,m,k)&=&nm+nk+mk-n-m-k+1+S(n-2,m-2,k-2)\\
&=&nm+nk+mk-n-m-k+1\\
&&+(n-2)(m-2)+(n-2)(k-2)+(m-2)(k-2)\\
&&-(n-2)-(m-2)-(k-2)+1+S(n-4,m-4,k-4)\\
&\vdots& \\
&=&nm+nk+mk-n-m-k+1+\cdots\\
&&+(n-(n-2))(m-(n-2))+(n-(n-2))(k-(n-2))\\
&&+(m-(n-2))(k-(n-2))\\
&&-(n-(n-2))-(m-(n-2))-(k-(n-2))+1\\
&&+S(0,m-n,k-n)\\
&=&\frac{1}{4}n(2mk+2m+2k-n),
\end{eqnarray*}
where the last equality can be arrived at by collecting like terms and using summation formulas (or can be conveniently computed by Mathematica). The expression for $S$ in the case when $n$ is odd can be obtained in a similar way.
\end{proof}



 Thus, in general three-dimensional arrays we can obtain a lower bound for the maximum number of diagonals, that is, $D(n,m,k) \geq S(n,m,k)$.
 It is natural to use the nested-shell arrangement  for general even-sided prisms,
 and investigate whether it provides an optimal solution as it did for tall even-sided prisms with a square base. To be able to do this, we extended the computer program to treat general three-dimensional arrays.
 The idea for the code is the same as before: the diagonal placement problem is converted to that of finding a maximum independent set in a graph whose vertices represent the
 space diagonals of the unit cubes in the array, and edges are drawn between those vertices whose corresponding diagonals have a common point. The code finds
 the maximum number of diagonals that can be placed in the array and depicts an arrangement of these diagonals as well.
 The nested-shell arrangement places 120 diagonals in the $4 \times 6 \times 8$ array, while our code constructs a solution
 with a maximum of $122$ diagonals. Hence, the nested-shell arrangement as described above does not provide an optimal solution in general, even in the case when all sides are even. Some experimentation with the computer code also suggests that $D(n,m,k)$ is strictly larger than $S(n,m,k)$ for $2\leq n\leq m \leq k$ unless $n=m$ and $n$ and $k$ are even (i.e., we have a tall even-sided prism with a square base). Thus, the nested-shell arrangement does not behave as the L-arrangement did in two dimensions, and $D(n,m,k)$ does not seem to reduce to $S(n,m,k)$ as the prisms get more and more elongated. However, we noticed that in all
 computed cases
  the maximum number of diagonals in even-sided arrays agreed with the upper bound in Proposition \ref{3dupbd}. Thus we strongly suspect that there is a general construction that
  achieves this upper bound when applied to any even-sided 3-D array.


\subsection{Two-layer arrays}
We continue with a somewhat trivial upper bound for $D$, which can nevertheless lead to a nice general result. If we consider any level of lattice points, with length $s$ and width $v$, then we can easily see that there cannot be more than $(s+1)\cdot (v+1)$ space diagonals that connect to these lattice points either by their lower or upper endpoint. So for example, in a $6 \times 6 \times 2$ array, there are three levels of lattice points, and the middle one has 49 potential endpoints for diagonals
that connect this level either to the one above or to the one below. This shows that $D(6,6,2)\leq 49$. Note that the array itself is made up of 72 unit cubes, so this
is a meaningful bound. Now, the crucial observation is that all lattice points in this middle level can be occupied except in a few cases. Indeed, we have the
following result.

\begin{proposition}
In an $n \times m \times 2$  two-layer array with $3\leq n\leq m$, $D(n,m,2)=(n+1)(m+1)$ unless $n=m=4$.
\end{proposition}

\begin{proof}
We will argue that each of the $(n+1)(m+1)$ lattice points of the middle level can serve as an endpoint of a diagonal in a valid arrangement. Let us start by placing diagonals going downward from the middle level originating at each of the lattice points along the boundary of the middle level except for the four corners, as depicted in green in the left panels of Figures \ref{fig:2l55} and \ref{fig:2l46}. Next, put diagonals originating in the four corners going upward (shown in purple in the right panels of Figures \ref{fig:2l55} and \ref{fig:2l46}). This takes care of the lattice points at the boundary of the middle level. Now consider the lattice points that are in the interior of the middle level. They form a rectangle as well, and we can place an upward diagonal originating at each of the non-corner lattice points on the boundary of this rectangle in a direction that is 45 degrees clockwise from a normal vector pointing outward from that edge of the rectangle. For lattice points at the corners of this inner rectangle, we use the following rule: the direction of the upward diagonal originating at the NE corner of the rectangle is SE, the direction of the diagonal at the  SE corner is SW, and the direction for the diagonals at the SW and NW corners is NW and NE, respectively. We can continue inward in this manner, placing upward diagonals at the lattice points on the boundary of each successive rectangle. If $n$ and $m$ are both odd, the construction can be completed this way. If $n \leq m$ and $n$ is even, then in the last step we arrive at a `degenerate rectangle', that is, a single lattice point at the center if $n = m$, or a line of $m - n + 1$ lattice points otherwise. If $n = m$ (with $n$ even), there is an available direction for an upward diagonal originating at the center point (unless $n = m = 4$). Similarly, if $n < m$ with $n$ even, the endpoints of the line of lattice points in the last step may have some directions blocked (for example, in the $4 \times 5$ or $4 \times 6$ cases), but there are enough directions available so that upward diagonals can be placed at each endpoint. Figures \ref{fig:2l55} and \ref{fig:2l46} illustrate the constructions described above.


\end{proof}

We remark that $D(4,4,2)=24$, and a solution with 24 diagonals can be obtained using the construction above for the $n=m$ (with $n$ even) case, but with no diagonal originating at the center point.
\vspace{0.5in}
\begin{figure}[h]
  \centering
    \includegraphics[height=1in]{fig3d2layer_new_5a55.eps}
\caption{Middle level of a $5\times 5\times 2$ array that contains a total of 36 diagonals. The downward diagonals are depicted in green on the left, while upward diagonals are shown in purple on the right. A small circle denotes the lattice point at which each diagonal originates.}
    \label{fig:2l55}
\end{figure}


\vspace{0.5in}

\begin{figure}
  \centering
    \includegraphics[height=.75in]{fig3d2layer_new_6a46.eps}
\caption{Middle level of a $4\times 6\times 2$ array that contains a total of 35 diagonals. The downward diagonals are depicted in green on the left, while upward diagonals are shown in purple on the right. A small circle denotes the lattice point at which each diagonal originates.}
    \label{fig:2l46}
\end{figure}

\newpage



\section{Open questions}

\begin{itemize}
\item[1.] Is $T(h,w)=D(h,w)$ for all  odd numbers $h,w \in \mathbb{Z}^+?$ That is, can a braided solution provide the maximum number of diagonals in an array for
any $h,w$ odd? If so, we can use Proposition \ref{formula} to obtain a general formula for $D$.
\item[2.]  Is it true that the upper bound for $D(2n,2m,2k)$  in Proposition \ref{3dupbd} is a lower bound as well? Is there a straightforward generalization of the two-dimensional L-arrangement that places the optimal number of diagonals in general even-sided rectangular prisms
in 3-D?
\item[3.] Does the placement of the optimal number of diagonals in rectangular prisms show some structure that is similar to the braids in the two-dimensional case?
\end{itemize}

\section{Acknowledgments}
The authors would like to thank Dr.\ G. Christopher Hruska and Dr.\ Jeb Willenbring for fruitful discussions and encouragement during the process of this investigation. The authors thank the referee for valuable suggestions regarding the improvement of this paper.


\begin{thebibliography}{9}
\raggedright

\bibitem{nrich}
Distinct Diagonals, NRICH enriching mathematics,
\url{http://nrich.maths.org/6784}.

\bibitem{Gardner}
M. Gardner, Some new results on non-attacking chess tasks, \emph{Math Horizons} \textbf{8} (2001) 10--12.

\bibitem{ibm}
IBM ILOG CPLEX Optimization Studio, Academic Initiative, \url{https://developer.ibm.com/academic/}.

\bibitem{pawns}
S. Kitaev and T. Mansour, The problem of the pawns, \emph{Ann. Comb.} \textbf{8} (2004) 81--91.

\bibitem{Kot}
V. Kot\v{e}\v{s}ovec, \emph{Non-attacking Chess Pieces --- 
Chess and Mathematics, Neohro\v{z}uj\'{\i}c\'{\i} se Kameny
--- \v{S}ach a Matematika},
 Self-published online book, 6th ed., 2013. Available at
\url{kotesovec.cz/books/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf}.

\bibitem{OEIS}
N. J. A. Sloane, The Online Encyclopedia of Integer Sequences,
\url{https://oeis.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15, 05B45.

\noindent \emph{Keywords: }
diagonal placement, maximum independent set, constrained optimization.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A264041} and
\seqnum{A260690}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  July 25 2016;
revised versions received  November 13 2016; December 2 2016; 
December 5 2016.
Published in {\it Journal of Integer Sequences}, December 27 2016.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}


.
