# Rainbow numbers of $[m]\times[n]$ for $x_{1}+x_{2}=x_{3}$

Kean Fallon  Department of Mathematics, Iowa State University, {keanpf,
jmiller0<EMAIL_ADDRESS>Ethan Manhart  Department of Mathematics and
Statistics, University of Wisconsin-La Crosse<EMAIL_ADDRESS><EMAIL_ADDRESS>Joe Miller  Department of Mathematics, Iowa State
University, {keanpf, jmiller0<EMAIL_ADDRESS>Hunter Rehm  Department
of Mathematics and Statistics, University of Vermont<EMAIL_ADDRESS>Nathan Warnberg  Department of Mathematics and Statistics, University of
Wisconsin-La Crosse<EMAIL_ADDRESS><EMAIL_ADDRESS>Laura
Zinnel  Department of Mathematics, Iowa State University, {keanpf, jmiller0,
<EMAIL_ADDRESS>
## Abstract

Consider the set $[m]\times[n]=\\{(i,j)\,:1\leq i\leq m,1\leq j\leq n\\}$ and
the equation $x_{1}+x_{2}=x_{3}$, namely $eq$. The _rainbow number of
$[m]\times[n]$ for $eq$_, denoted $\operatorname{rb}([m]\times[n],eq)$, is the
smallest number of colors such that for every surjective
$\operatorname{rb}([m]\times[n],eq)$-coloring of $[m]\times[n]$ there must
exist a solution to $eq$, with component-wise addition, where every element of
the solution set is assigned a distinct color. This paper determines that
$\operatorname{rb}([m]\times[n],eq)=m+n+1$ for all values of $m$ and $n$ that
a greater than or equal to $2$.

Keywords: rainbow, anti-Ramsey, Schur

##  1 Introduction

Given a set $S$, a coloring of $S$ assigns each element a color. Ramsey theory
is the study of guaranteeing monochromatic structures in $S$. On the other
hand, anti-Ramsey theory is the study of guaranteeing polychromatic (or
rainbow) structures in $S$ and has gained the interest of many authors when
$S$ is $[n]=\\{1,2,\dots,n\\}$ or $\mathbb{Z}_{n}$ [1, 2, 5, 8, 9, 10]. As an
example, the anti-van der Waerden number on $[n]$, denoted
$\operatorname{aw}([n],k)$, is the smallest number of colors such that every
exact (onto) $\operatorname{aw}([n],k)$-coloring of $[n]$ is guaranteed to
have an arithmetic progression of length $k$ where each element of the
progression is colored distinctly, [4, 6, 13]. The anti-van der Waerden number
has also been studied in graphs, [3, 11, 12], on finite abelian groups, [14],
and were generalized further on $\mathbb{Z}_{n}$ for linear equations, [1, 5,
8, 10]. This inspired the authors in [7] to look into rainbow numbers of $[n]$
for linear equations.

The rainbow number of $[n]$ for $eq$, denoted $\operatorname{rb}([n],eq)$, is
the smallest number of colors such that for every exact
$\operatorname{rb}([n],eq)$-coloring of $[n]$, there exists a solution to $eq$
with every member of the solution set assigned a distinct color. In this
paper, the rainbow number of $[n]\times[m]$ for equation $x_{1}+x_{2}=x_{3}$
is solved completely. Section 2 establishes vocabulary, contains preliminary
results and provides Examples and Figures that are referenced throughout the
paper. Each section following contains a case analysis that ultimately leads
to a complete solution. Section 3 analyzes $(m+n+1)$-colorings of
$[m]\times[n]$ when the main diagonal has three colors. The analysis continues
into Section 4 when the main diagonal has four or more colors. Finally,
Section 5 discusses some forbidden structures in rainbow-free
$(m+n+1)$-colorings of $[m]\times[n]$ and completes the analysis.

##  2 Preliminaries

An _$r$ -coloring_ of a set $S$ is a function $c:S\to[r]$, where
$[r]=\\{1,2,\dots,r\\}$, and an $r$-coloring is _exact_ if it is surjective.
If $X\subseteq S$, then $c(X)=\\{c(x)\,:\,x\in X\\}$. Given an equation $eq$,
a solution in $S$ to $eq$ is a subset of elements of $S$ that satisfy the
equation. A solution $s$ is a _rainbow solution to $eq$ with respect to
coloring $c$_ if the colors of the elements of $s$ are pairwise distinct. If
context is clear the reference to the coloring $c$ will be dropped and ‘$s$ is
a rainbow solution’ will often be used. The _rainbow number of $S$ for $eq$_,
denoted $\operatorname{rb}(S,eq)$, is the smallest number such that every
exact $\operatorname{rb}(S,eq)$-coloring of $S$ contains a rainbow solution to
$eq$. A coloring of $S$ that has no rainbow solutions to $eq$ is called
_rainbow-free_. Although solutions to $eq$ are sets, they will often be
thought of as lists. That is, if it is claimed that
$\\{\alpha,\beta,\gamma\\}$ is a solution then, in most cases,
$\alpha+\beta=\gamma$. Solutions with repeated elements cannot be rainbow and
will be referred to as _degenerate_. If a set $S$ has no solutions to $eq$
then the convention is that $\operatorname{rb}(S,eq)=|S|+1$.

Throughout the paper the set $S$ that will be discussed is
$[m]\times[n]=\\{(i,j):i,j\in\mathbb{Z},1\leq i\leq m\text{ and }1\leq j\leq
n\\}$, with $m\leq n$, and the equation, $eq$, is $x_{1}+x_{2}=x_{3}$. Note
that addition is component-wise and that if $m=1$ there are no solutions so,
following convention, $\operatorname{rb}([1]\times[n])=n+1$.

Define the _$k^{th}$ diagonal_ $D_{k}$ as the set

$D_{k}=\big{\\{}(i,j)\in[m]\times[n]\,:\,m-k=i-j\big{\\}}.$

For reference, the authors view the array with $m$ rows and $n$ columns and
the upper left element as $(1,1)$ thus, $D_{1}=\\{(m,1)\\}$ and is in the
bottom left corner. The diagonal $D_{m}$ is called the _main diagonal_. A
diagonal that is not the main diagonal will be referred to as an _off-
diagonal_. Observe that $[m]\times[n]$ has $m+n-1$ diagonals.

Definition 2.1 was established by the authors in [7].

######  Definition 2.1.

[7] Let $c$ be an exact $r$-coloring of $[n]$. Define
$\mathcal{C}_{i}=\\{a\in[n]\,:\,c(a)=i\\}$ and $s_{i}\in\mathcal{C}_{i}$ such
that $s_{i}$ is the smallest element of $\mathcal{C}_{i}$ for each color $i$.
Note that for any exact $r$-coloring $c$, it is always possible to have
$s_{i}<s_{j}$ for $i<j$.

A modified definition is introduced for the purposes of this paper. Let $c$ be
a coloring of $[m]\times[n]$. Without loss of generality, it can and will be
assumed that if $|c(D_{m})|=\ell$, then $c(D_{m})=\\{1,2,\dots,\ell\\}$. Now,
define $s_{1}=1$ and for $k\geq 2$, define

$\displaystyle s_{k}=\min_{1\leq x\leq m}\big{\\{}x:c((x,x))\neq
c((s_{j},s_{j}))\textrm{ for all $j<k$}\big{\\}}.$

For any exact $r$-coloring $c$, it is always possible to have $s_{i}<s_{j}$
for $i<j$. If that is not the case, say $s_{i}>s_{j}$ and $i<j$, an isomorphic
coloring can be created by swapping the color of any element with color $i$ to
have color $j$ and vice versa. Thus, it will also be assumed that
$s_{i}<s_{j}$ when $i<j$.

In [7], rainbow numbers for the set $[m]$ for equation $x_{1}+x_{2}=x_{3}$ are
investigated. Note that that main diagonal of $[m]\times[n]$ behaves similarly
to $[m]$, thus results from [7] can be applied to the main diagonal. Further,
$s_{i}$ in Lemma 2.2 is defined similarly to the $s_{i}$ established in this
paper.

The following four results are from [7] or extensions of results from [7] to
$[m]\times[n]$. In particular, Lemma 2.5 limits the number of colors that can
appear in $D_{m}$. The wording has been modified to match the language used in
this paper.

######  Lemma 2.2.

[7] Let $c$ be an exact, rainbow-free $r$-coloring of $[m]$ for
$x_{1}+x_{2}=x_{3}$, with color set $\\{0,1,\dots,r-1\\}$, then

  1. 1.

if $s_{i}=\ell$, then $2\ell\leq s_{i+1}$ for $0\leq i\leq r-2$,

  2. 2.

$2^{i}\leq s_{i}$ for $0\leq i\leq r-1$.

######  Corollary 2.3.

If $c$ is a rainbow-free coloring of $[m]$ and $\ell=|c([m])|$, then
$2^{i-2}s_{2}\leq s_{i}$ for $2\leq i\leq\ell$. In particular,
$2^{\ell-2}s_{2}\leq m$.

###### Proof.

The proof will proceed by induction on $i$. The base case, when $i=2$, is
clear. As the inductive hypothesis, assume for some $2\leq j\leq\ell-1$ that
$2^{j-2}s_{2}\leq s_{j}$ which gives $2^{j-1}s_{2}\leq 2s_{j}$. Further, by
Lemma 2.2 part 1, $2s_{j}\leq s_{j+1}$. Therefore, $2^{j-1}s_{2}\leq s_{j+1}$
which completes the induction.∎

######  Theorem 2.4.

[7] For $m\geq 3$,
$\operatorname{rb}([m],x_{1}+x_{2}=x_{3})=\left\lfloor\log_{2}(m)+2\right\rfloor$.

######  Lemma 2.5.

If $c$ is a rainbow-free coloring of $[m]\times[n]$ for $eq$ with $m\leq n$,
then $|c(D_{m})|\leq\left\lfloor\log_{2}(m)+1\right\rfloor$ and
$|c(D_{m})|\leq\log_{2}(m/s_{2})+2$.

###### Proof.

Note that solutions to $x+y=z$ in $D_{m}$ correspond bijectively to solutions
to $x+y=z$ in $[m]$, so Theorem 2.4 can be applied to $D_{m}$. This gives
$|c(D_{m})|\leq\left\lfloor\log_{2}(m)+1\right\rfloor$ immediately. Further,
define $\ell=|c(D_{m})|$ and note that Corollary 2.3 implies
$2^{\ell-2}s_{2}\leq m$, thus $\ell\leq\log_{2}(m/s_{2})+2$, as desired.∎

Lemma 2.6 provides an exact, $(m+n)$-coloring that avoids rainbow solutions
which establishes a lower bound on $\operatorname{rb}([m]\times[n],eq).$ The
remaining results analyze the appearance of solutions to $eq$ in
$[m]\times[n]$ and the structure of a rainbow-free coloring on $[m]\times[n]$
to help establish an upper bound on $\operatorname{rb}([m]\times[n],eq)$.

######  Lemma 2.6.

For $2\leq m\leq n$, $m+n+1\leq\operatorname{rb}([m]\times[n],eq)$.

###### Proof.

Let $c:[m]\times[n]\to[m+n]$ be defined by

$c((i,j))=\left\\{\begin{array}[]{ll}1&\text{if $i<m$ and $j<n$,}\\\
i+1&\text{if $i<m\text{ and }j=n$,}\\\ j+m&\text{if
$i=m$.}\par\end{array}\right.$

Note that $(1,n)$ and $(m,1)$ are not in any solution to $eq$. If
$\alpha,\beta,\gamma\in[m]\times[n]$ such that $\alpha+\beta=\gamma$, then
$c(\alpha)=c(\beta)=1$. Therefore, $c$ is rainbow-free for $eq$ and
$m+n+1\leq\operatorname{rb}([m]\times[n],eq).$ ∎

######  Lemma 2.7.

If $c$ is a rainbow-free coloring of $[m]\times[n]$ for $eq$ with $m\leq n$,
then, for all $D_{x}$ with $x\neq m$, $\big{|}c(D_{x})\setminus
c\big{(}D_{m}\big{)}\big{|}\leq 1$.

###### Proof.

If $m=1$ each diagonal has one element and the result follows. Thus, assume
$2\leq m$. Since $|D_{1}|=|D_{m+n-1}|=1$, it is certainly true that
$|c(D_{1})\setminus c(D_{m})|\leq 1$ and $|c(D_{m+n-1})\setminus c(D_{m})|\leq
1$.

For the purpose of contradiction, assume $1<x<m+n-1$ and $|c(D_{x})\setminus
c(D_{m})|\geq 2$. Then there exists $\beta$, $\gamma\in D_{x}$ such that
$c(\beta),c(\gamma)\in c(D_{x})\setminus c(D_{m})$. However, there exists
$\alpha\in D_{m}$ such that $\\{\alpha,\beta,\gamma\\}$ is a rainbow solution,
a contradiction. Thus, $\big{|}c(D_{x})\setminus
c\big{(}D_{m}\big{)}\big{|}\leq 1$. ∎

Corollary 2.8 follows quickly from Lemmas 2.6 and 2.7. This allows most of the
rest of the paper to focus on the situation when $3\leq m\leq n$.

######  Corollary 2.8.

If $m=2$ and $m\leq n$, then $\operatorname{rb}([m]\times[n])=m+n+1$.

######  Corollary 2.9.

If $c$ is an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for $eq$
with $3\leq m\leq n$, then $|c(D_{m})|\geq 3$.

###### Proof.

Lemma 2.7 implies $\big{|}c(D_{x})\setminus c(D_{m})\big{|}\leq 1$ for all
$x\neq m$. So, $\big{|}c\big{(}[m]\times[n]\big{)}\setminus
c(D_{m})\big{|}\leq m+n-2$. Thus, $|c(D_{m})|\geq 3$. ∎

Let $c$ be a coloring of $[m]\times[n]$. Diagonal $D_{j}$ _contributes color
$x$_ if $x\in c(D_{j})\backslash c(D_{m})$ and $x\notin c(D_{i})$ for all
$i<j$. Otherwise, $D_{j}$ does not contribute color $x$. In general, if
$D_{j}$ contributes any color it is a _contributing diagonal_ and if it does
not contribute any color it is a _non-contributing diagonal_.

Lemma 2.10 and the proceeding corollary establish results related to
contributing off-diagonals. In particular, they provide an upper bound on the
number of non-contributing off-diagonals and, subsequently, a lower bound on
the number of contributing off-diagonals. This furthers the restrictions that
applying an exact, rainbow-free $(m+n+1)$-coloring has on $[m]\times[n]$ when
the main diagonal has exactly three colors, as in Lemma 3.1, when the main
diagonal has exactly four or more colors, as in Theorem 4.9, and more
generally in Lemma 5.1.

######  Lemma 2.10.

If $c$ is an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ with
$3\leq m\leq n$, then there are at most $|c(D_{m})|-3$ off-diagonals that do
not contribute a color.

###### Proof.

Define $\ell=|c(D_{m})|$ and note that there are $m+n-2$ off-diagonals and
$m+n+1-\ell$ colors that appear in the off-diagonals that do not appear in the
main diagonal. Let $k$ be the number of off-diagonals that do not contribute a
color. For the sake of contradiction, assume $k\geq\ell-2$. This implies
$m+n-2-k\leq m+n-\ell$ off-diagonals must contribute a color. Thus, by the
pigeon hole principle, some off-diagonal contains two colors that do not
appear in the main diagonal. Since $c$ was assumed to be rainbow-free, Lemma
2.7 is contradicted. Therefore, $k\leq\ell-3$.∎

######  Corollary 2.11.

If $c$ is an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ with
$3\leq m\leq n$, then there are at least $m+n-1-\log_{2}(m/s_{2})$
contributing off-diagonals.

###### Proof.

Define $\ell=|c(D_{m})|$ and observe that Lemma 2.10 indicates that there are
at most $\ell-3$ non-contributing off-diagonals. Since there are $m+n-2$ off-
diagonals in total, and off-diagonals are either contributing or non-
contributing, there are at least $(m+n-2)-(\ell-3)=m+n-\ell+1$ contributing
off-diagonals. Since Lemma 2.5 implies $\ell\leq\log_{2}(m/s_{2})+2$, there
are at least $m+n-\log_{2}(m/s_{2})-1$ contributing off-diagonals.∎

Let $\alpha=(a_{1},a_{2})\in D_{a}$ and $\beta=(b_{1},b_{2})\in D_{b}$ with
$a\neq b$. If $a_{1}<b_{1}$ and $a_{2}<b_{2}$, there is a _jump from $\alpha$
to $\beta$_ and the _jump distance_ is defined to be
$(b_{1}-a_{1})+(b_{2}-a_{2})$. Alternatively, there is a jump from $\alpha$ to
$\beta$ when there exists some $\delta\in[m]\times[n]$ such that
$\alpha+\delta=\beta$, where $\delta=(d_{1},d_{2})$ is called _the jump_ from
$\alpha$ to $\beta$ and has jump distance $d_{1}+d_{2}$.

######  Example 2.12.

In Figure 1, $\alpha=(2,7)$, $\beta=(4,11)$, $\gamma=(5,2)$ and $\tau=(7,3)$.
The jump from $\alpha$ to $\beta$ is $\delta=(2,4)$ and has jump distance $6$.
The jump from $\gamma$ to $\tau$ is $(2,1)$ and has jump distance $3$.

When there is a jump from $\alpha=(a_{1},a_{2})$ to $\beta=(b_{1},b_{2})$ with
$\alpha\in D_{a}$ and $\beta\in D_{b}$, certain diagonals exhibit the special
property that all elements within the diagonals make additional jumps with
$\alpha$ or $\beta$. This set of diagonals is

$S:=\\{D_{x}\leavevmode\nobreak\ |\leavevmode\nobreak\
m+a_{2}-b_{1}<x<m+b_{2}-a_{1}\text{ and }x\notin\\{a,b,m\\}\\}.$ (1)

To visualize this, a rectangle is drawn using $\alpha$ and $\beta$ as corners.
The diagonals with indices between $m+a_{2}-b_{1}$ and $m+b_{2}-a_{1}$ are
those that intersect this rectangle not including the lower left and upper
right corners. To finalize $S$, simply remove the diagonals containing
$\alpha$ and $\beta$ and the main diagonal if applicable.

$\alpha$$\beta$$\gamma$$\tau$ Figure 1: Jumps from $\alpha$ to $\beta$ and
from $\gamma$ to $\tau$ from Example 2.12. Also, a visualization of the set of
diagonals $S$ (in gray) with respect to $\alpha$ and $\beta$.

The next two lemmas will show that if $\gamma$ is in a diagonal of $S$, then
either $\alpha$ makes a jump to $\gamma$ or $\gamma$ makes a jump to $\beta$.
Lemma 2.13 will show this for all diagonals of $S$ between $D_{a}$ and
$D_{b}$, and Lemma 2.14 will consider the remainder of the diagonals in $S$.

######  Lemma 2.13.

Suppose there is a jump from $\alpha=(a_{1},a_{2})\in D_{a}$ to
$\beta=(b_{1},b_{2})\in D_{b}$. If $\gamma=(g_{1},g_{2})\in D_{g}$ such that
$a<g<b$ or $b<g<a$, then either $\alpha$ makes a jump to $\gamma$ or $\gamma$
makes a jump to $\beta$.

###### Proof.

Since there is a jump from $\alpha$ to $\beta$, it follows that $a_{1}<b_{1}$
and $a_{2}<b_{2}$.

If $a<g<b$, then $m-a_{1}+a_{2}<m-g_{1}+g_{2}<m-b_{1}+b_{2}$, so

$a_{2}-a_{1}<g_{2}-g_{1}<b_{2}-b_{1}.$

Suppose $g_{1}<b_{1}$. Then $g_{2}-g_{1}<b_{2}-b_{1}<b_{2}-g_{1}$ which
implies $g_{2}<b_{2}$. Thus, $\gamma$ makes a jump to $\beta$.

On the other hand, suppose $b_{1}\leq g_{1}$. In this case $a_{1}<b_{1}\leq
g_{1}$, so $a_{2}-g_{1}<a_{2}-a_{1}<g_{2}-g_{1}$. This yields $a_{2}<g_{2}$.
which means $\alpha$ makes a jump to $\gamma$.

The case where $b<g<a$ leads to a similar argument and the desired
conclusion.∎

######  Lemma 2.14.

Suppose there is a jump from $\alpha=(a_{1},a_{2})\in D_{a}$ to
$\beta=(b_{1},b_{2})\in D_{b}$ and define
$\ell=\min\\{b_{1}-a_{1},b_{2}-a_{2}\\}$.

  1. a.)

If $a<b$ and $\gamma\in D_{g}$ such that $a-\ell<g<a$ or $b<g<b+\ell$, then
either there is a jump from $\alpha$ to $\gamma$ or there is a jump from
$\gamma$ to $\beta$.

  2. b.)

If $b<a$ and $\gamma\in D_{g}$ such that $b-\ell<g<b$ or $a<g<a+\ell$, then
either there is a jump from $\alpha$ to $\gamma$ or there is a jump from
$\gamma$ to $\beta$.

###### Proof.

Let $a<b$ and $\gamma=(g_{1},g_{2})\in D_{g}$ and first consider $a-\ell<g<a$.
If $a_{2}<g_{2}$, then $a_{2}-g_{1}<g_{2}-g_{1}<a_{2}-a_{1}$ implying
$a_{1}<g_{1}$ and $\alpha$ makes a jump to $\gamma$. Alternatively, suppose
$g_{2}\leq a_{2}$. Since $a_{2}<b_{2}$, it follows that $g_{2}<b_{2}$. Note
that $a-\ell<g<a$ implies $a_{2}-a_{1}-\ell<g_{2}-g_{1}<a_{2}-a_{1}$. This
yields $g_{1}<a_{1}+\ell$. Since $\ell\leq b_{1}-a_{1}$, it follows that
$g_{1}<b_{1}$. Thus, $\gamma$ makes a jump to $\beta$.

Second, consider $b<g<b+\ell$. If $g_{2}<b_{2}$, then
$g_{2}-b_{1}<b_{2}-b_{1}<g_{2}-g_{1}$ implying $g_{1}<b_{1}$, and there is a
jump from $\gamma$ to $\beta$. Alternatively, suppose $b_{2}\leq g_{2}$. Since
$a_{2}<b_{2}$, it follows that $a_{2}<g_{2}$. Then $b<g<b+\ell$ implies
$b_{2}-b_{1}<g_{2}-g_{1}<b_{2}-b_{1}+\ell$. This yields $b_{1}-\ell<g_{1}$.
Since $\ell\leq b_{1}-a_{1}$, it follows that $a_{1}<g_{1}$. Thus, $\alpha$
makes a jump to $\gamma$.

The result when $b<a$ follows from a similar argument. ∎

Lemma 2.15 says that given the diagonal of two elements the diagonal of the
sum and difference of the elements lands in. For this reason, the authors
refer to this as the ‘Landing Lemma.’ This lemma becomes important quickly, as
many succeeding proofs require a working knowledge of the locations of
contributing diagonals, non-contributing diagonals, or elements of a jump.

######  Lemma 2.15 (Landing Lemma).

If $\alpha\in D_{a}$, $\beta\in D_{b}$, and $\alpha+\beta\in[m]\times[n]$,
then $\alpha+\beta\in D_{a+b-m}$. Similarly, if $\alpha-\beta\in[m]\times[n]$
then $\alpha-\beta\in D_{a-b+m}.$

###### Proof.

Let $\alpha=(a_{1},a_{2})$ and $\beta=(b_{1},b_{2})$ and suppose
$\alpha+\beta\in D_{k}$ for some appropriately defined $k$. Then,
$m-a=a_{1}-a_{2}$ and $m-b=b_{1}-b_{2}$. Moreover,
$m-k=a_{1}+b_{1}-(a_{2}+b_{2})$ and thus

$k=m-(a_{1}+b_{1})+a_{2}+b_{2}=a+b-m.$

A similar analysis gives that $\alpha-\beta\in D_{a-b+m}$. ∎

Let $c$ be a coloring of $[m]\times[n]$. Recall,
$s_{2}=\min\\{x\leavevmode\nobreak\ |\leavevmode\nobreak\ c((x,x))\neq
c((1,1))\\}$. Define $W_{1}=\\{(x,y)\in[m]\times[n]\leavevmode\nobreak\
|\leavevmode\nobreak\ (x,y)+(s_{2},s_{2})\in[m]\times[n]\\}$,
$W_{2}=\\{(x,y)\in[m]\times[n]\leavevmode\nobreak\ |\leavevmode\nobreak\
(x,y)-(s_{2},s_{2})\in[m]\times[n]\\}$, and $W=W_{1}\cup W_{2}$. See Figure 2
for a visualization of these, and the following, definitions.

The next definitions will not be used until Section 5 but are included here as
they are closely related to $W$, $W_{1}$ and $W_{2}$. Define
$Y_{1}=\\{(x,y)\in[m]\times[n]:m<x+s_{2}\text{ and }y-s_{2}<0\\}$,
$Y_{2}=\\{(x,y)\in[m]\times[n]:x-s_{2}<0\text{ and }m<y+s_{2}\\}$, and
$Y=Y_{1}\cup Y_{2}$.

Let $c$ be a coloring of $[m]\times[n]$. If $\alpha\in D_{a},\beta\in D_{a+1}$
where $D_{a}$ and $D_{a+1}$ are contributing, and $c(\alpha),c(\beta)\notin
c(D_{m})$, then $\\{\alpha,\beta\\}$ are a _consecutive contributing pair of
elements_. If $\\{\alpha,\beta\\}$ is a consecutive contributing pair of
elements with $\alpha=(a_{1},a_{2})$ and $\beta=(a_{1},a_{2}+1)$, then
$\\{\alpha,\beta\\}$ is a _horizontal pair_ and if $\alpha=(a_{1},a_{2})$ and
$\beta=(a_{1}-1,a_{2})$, then $\\{\alpha,\beta\\}$ is a _vertical pair_. Let
$P_{v}$ be a vertical pair, $P_{h}$ be a horizontal pair, and define
$P=P_{v}\cup P_{h}$. If $P_{v}\cap P_{h}=\emptyset$, $P_{v}\cap
W\neq\emptyset$, and $P_{h}\cap W\neq\emptyset$, $P$ is called a _contributing
disjoint corner_.

$h_{1}$$h_{2}$$v_{1}$$v_{2}$$(s_{2},s_{2})$$W_{1}$$W_{2}$$Y_{1}$$Y_{2}$$P_{h}$$P_{v}$
Figure 2: An example of $[m]\times[n]$ when $(s_{2},s_{2})=(3,3)$ with
corresponding $Y_{1}$, $Y_{2}$, $W_{1}$ and $W_{2}$ highlighted. Further, a
contributing disjoint corner, $P_{h}\cup P_{v}$, with
$c(h_{1}),c(h_{2}),c(v_{1})$ and $c(v_{2})$ pairwise distinct, is shown.

Lemma 2.16 says that a contributing disjoint corner will force a rainbow
solution in $[m]\times[n]$. The proof of Theorem 3.4 uses Lemma 2.16 to arrive
at a contradiction once a contributing disjoint corner is found.

######  Lemma 2.16.

If $c$ is a rainbow-free coloring of $[m]\times[n]$ for $eq$ with $m\leq n$,
then there are no contributing disjoint corners $P=P_{v}\cup P_{h}$ in
$[m]\times[n]$.

###### Proof.

If $|c(D_{m})|=1$, then $(s_{2},s_{2})$ does not exist and $W$ is not defined
so the statement is vacuously true. Therefore, let $2\leq|c(D_{m})|$. For the
sake of contradiction, assume $P_{v}=\\{(a_{1},b_{1}),(a_{1}-1,b_{1})\\}$ and
$P_{h}=\\{(a_{2},b_{2}),(a_{2},b_{2}+1)\\}$ form a contributing disjoint
corner. Define $c_{3}=c((a_{1},b_{1}))$, $c_{4}=c((a_{1}-1,b_{1}))$,
$c_{5}=c((a_{2},b_{2}))$, and $c_{6}=c((a_{2},b_{2}+1))$, and recall that
convention implies $c((1,1))=1$ and $c((s_{2},s_{2}))=2$. Note that
$1,2,c_{3},c_{4},c_{5}$ and $c_{6}$ are pairwise distinct. It will be shown
that every possible color of $(s_{2}-1,s_{2})$ gives a rainbow solution, which
is a contradiction.

First, note that $P_{v}$ either intersects $W_{1}$ or $W_{2}$. Suppose
$P_{v}\cap W_{1}\neq\emptyset$. Then $(a_{1}-1,b_{1})\in W_{1}$ implying that
the elements of

$(a_{1}-1,b_{1})+(s_{2},s_{2})=(a_{1}-1+s_{2},b_{1}+s_{2})$

are in $[m]\times[n]$. Further, this equation implies that
$c((a_{1}-1+s_{2},b_{1}+s_{2}))\in\\{2,c_{4}\\}$. So, the equation

$(a_{1},b_{1})+(s_{2}-1,s_{2})=(a_{1}-1+s_{2},b_{1}+s_{2})$

implies that $c((s_{2}-1,s_{2}))\in\\{2,c_{3},c_{4}\\}$. Alternatively, if
$P_{v}\cap W_{2}\neq\emptyset$, then $(a_{1},b_{1})\in W_{2}$. Similar to the
previous case, the equations

$(a_{1}-s_{2},b_{1}-s_{2})+(s_{2},s_{2})=(a_{1},b_{1})$

and

$(a_{1}-s_{2},b_{1}-s_{2})+(s_{2}-1,s_{2})=(a_{1}-1,b_{1})$

imply that $c((s_{2}-1,s_{2}))\in\\{2,c_{3},c_{4}\\}$.

Second, note that $P_{h}$ either intersects $W_{1}$ or $W_{2}$. If $P_{h}\cap
W_{1}\neq\emptyset$, then $(a_{2},b_{2})\in W_{1}$. So,
$(a_{2}+s_{2},b_{2}+s_{2})\in[m]\times[n]$. Since
$a_{2}<a_{2}+s_{2}-1<a_{2}+s_{2}$, it follows that
$(a_{2}+s_{2}-1,b_{2}+s_{2})\in[m]\times[n]$. Thus, the equation

$(a_{2},b_{2}+1)+(s_{2}-1,s_{2}-1)=(a_{2}+s_{2}-1,b_{2}+s_{2})$

implies $c((a_{2}+s_{2}-1,b_{2}+s_{2}))\in\\{1,c_{6}\\}$ because
$c((s_{2}-1,s_{2}-1))=1$. Finally, the equation

$(a_{2},b_{2})+(s_{2}-1,s_{2})=(a_{2}+s_{2}-1,b_{2}+s_{2})$

implies $c((s_{2}-1,s_{2}))\in\\{1,c_{5},c_{6}\\}$. On the other hand, if
$P_{h}\cap W_{2}\neq\emptyset$, then $(a_{2},b_{2}+1)\in W_{2}$ and the
equations

$(a_{2}-s_{2}+1,b_{2}-s_{2}+1)+(s_{2}-1,s_{2})=(a_{2},b_{2}+1)$

and

$(a_{2}-s_{2}+1,b_{2}-s_{2}+1)+(s_{2}-1,s_{2}-1)=(a_{2},b_{2})$

imply that $c((s_{2}-1,s_{2}))\in\\{1,c_{5},c_{6}\\}$.

Therefore, no matter where $P_{v}$ and $P_{h}$ are in $[m]\times[n]$,
$c((s_{2}-1,s_{2}))\in\\{2,c_{3},c_{4}\\}\cap\\{1,c_{5},c_{6}\\}$, a
contradiction. ∎

##  3 Main diagonal has three colors

This section focuses on the situation where $[m]\times[n]$ has an exact
$(m+n+1)$-coloring and the main diagonal has exactly three colors. The overall
strategy of the section is to analyze the structure of an arbitrary coloring,
with the previously stated assumptions, and show that the structural
restrictions must admit a rainbow solution to $eq$.

Lemma 3.1 is a direct consequence of Lemmas 2.7 and 2.10.

######  Lemma 3.1.

If $c$ is an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for $eq$
with $3\leq m\leq n$ and $|c(D_{m})|=3$, then each off-diagonal $D_{k}$
contributes exactly one color $c_{k}$ such that $c_{k}\notin
c([m]\times[n]\setminus D_{k})$.

Lemma 3.2 proves that there are no jumps between distinctly colored elements
when there are three colors in the main diagonal. A brief outline of the
argument follows. First, it is shown that if such a jump exists between
elements in $D_{a}$ and $D_{b}$, then there is a $k$ such that $a=m+k$, and
$b=m+2k$. Then, it is shown that $|k|=1$, so either $a=m+1$ and $b=m+2$ or
$a=m-1$ and $b=m-2$. This ultimately forces $\alpha=(1,2)$ or $\alpha=(2,1)$,
respectively. Finally, two cases pertaining to the size of $s_{3}$ lead to
contradictions.

######  Lemma 3.2.

If $c$ is an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for $eq$
with $3\leq m\leq n$ and $|c(D_{m})|=3$, then there are no jumps from $\alpha$
to $\beta$ with $c(\alpha),c(\beta)\notin c(D_{m})$ and $c(\alpha)\neq
c(\beta)$.

###### Proof.

Suppose there is a jump from $\alpha\in D_{a}$ to $\beta\in D_{b}$ with
$c(\alpha),c(\beta)\notin c(D_{m})$ and $c(\alpha)\neq c(\beta)$. There must
exist some $\delta\in D_{t}$ with $\alpha+\delta=\beta$, and
$c(\delta)\in\\{c(\alpha),c(\beta)\\}$. If $t\notin\\{a,b,m\\}$, then Lemma
3.1 is contradicted. Further, $t\neq m$ because $c(\delta)\notin c(D_{m})$,
and $t\neq b$ because $\alpha\notin D_{m}$. Thus, $t=a$,
$c(\delta)=c(\alpha)$, and Lemma 2.15 implies $b=2a-m$.

Define $k=a-m$ so that $a=m+k$ and $b=m+2k$. For the sake of contradiction,
assume $1<|k|$. Then there exist some off-diagonal $D_{g}$ with $g$ strictly
between $a$ and $b$. By Lemma 3.1, $D_{g}$ must contribute a color, say
$D_{g}$ contributes $c(\gamma)$ for some $\gamma\in D_{g}$. Lemma 2.13 implies
that there must be either a jump from $\alpha$ to $\gamma$ or a jump from
$\gamma$ to $\beta$. In either case, there exists some $\delta^{\prime}\in
D_{t^{\prime}}$ such that $\alpha+\delta^{\prime}=\gamma$ or
$\gamma+\delta^{\prime}=\beta$, and Lemma 2.15 implies
$t^{\prime}\in\\{m+g-a,m+b-g\\}$. For the sake of contradiction, assume
$t^{\prime}\in\\{a,b,m,g\\}$ implying
$t^{\prime}\in\\{a,b,m,g\\}\cap\\{m+g-a,m+b-g\\}$. Since $g$ is strictly
between $a$ and $b$, $g=m+k+j$ for some $j$ strictly between $0$ and $k$.
Converting all elements in the two sets to be in terms of $m$, $k$ and $j$
gives

$t^{\prime}\in\\{m+k,m+2k,m,m+k+j\\}\cap\\{m+j,m+k-j\\}.$

Note that the restrictions on $j$, and the fact that $1<|k|$, imply $m+j$ and
$m+k-j$ are strictly between $m$ and $m+k$. Thus, the intersection is empty
and $t^{\prime}\notin\\{a,b,m,g\\}$. Since $c$ is rainbow-free,
$c(\delta^{\prime})\in\\{c(\alpha),c(\beta),c(\gamma)\\}$. This contradicts
Lemma 3.1.

This means $|k|=1$, which implies that $a=m+1$ and $b=m+2$ or $a=m-1$ and
$b=m-2$. First, consider the case where $a=m+1$ and $b=m+2$. Assume for the
sake of contradiction that
$\alpha=(a_{1},a_{2}),\beta=(b_{1},b_{2}),\delta=(t_{1},t_{2})$ are defined
such that $2\leq a_{1},t_{1}$. Since $2\leq a_{1},t_{1}$, it must be the case
that $4\leq b_{1}$. Additionally, note that $D_{m+3}$ contributes
$c(\gamma^{\prime})$ for some $\gamma^{\prime}=(g_{1},g_{2})\in D_{m+3}$ by
Lemma 3.1. Since $\alpha\in D_{m+1}$, $\beta\in D_{m+2}$, $\delta\in D_{m+1}$,
$\text{ and }\gamma^{\prime}\in D_{m+3}$, the equations:

$\displaystyle a_{2}=a_{1}+1$ (2) $\displaystyle t_{2}=t_{1}+1$ (3)
$\displaystyle g_{2}=g_{1}+3$ (4)

hold. Using the above information, it will be shown that irrespective of the
location of $\gamma^{\prime}=(g_{1},g_{2})$ in the diagonal $D_{m+3}$ a
contradiction can be found.

Case 1.

Suppose $a_{1}<g_{1}$.
Equations (2) and (4) give $a_{2}=a_{1}+1<a_{1}+3<g_{1}+3=g_{2}$. Since
$a_{1}<g_{1}$ and $a_{2}<g_{2}$ there is a jump from $\alpha$ to
$\gamma^{\prime}$, so by Lemma 2.15 there exists a $\delta^{\prime}\in
D_{m+2}$ such that $\alpha+\delta^{\prime}=\gamma^{\prime}$. Since $c$ is a
rainbow-free coloring,
$c(\delta^{\prime})\in\\{c(\alpha),c(\gamma^{\prime})\\}$. However, $D_{m+2}$
contributes the color $c(\beta)$ so Lemma 2.7 is contradicted.

Case 2.

Suppose $g_{1}\leq a_{1}$.
Since there is a jump from $\alpha$ to $\beta$, $a_{1}<b_{1}$ and
$a_{2}<b_{2}$. Thus, $g_{1}<b_{1}$. Equations (2) and (4) give $g_{2}\leq
a_{2}+2$. Further, Equation (3) implies $t_{1}\leq 3$, so
$\alpha+\delta=\beta$ gives $a_{2}+3\leq a_{2}+t_{2}=b_{2}$. So $g_{2}<b_{2}$.
This implies there is a jump from $\gamma^{\prime}$ to $\beta$, so by Lemma
2.15 there exists a $\delta^{\prime}\in D_{m-1}$ such that
$\gamma^{\prime}+\delta^{\prime}=\beta$. Lemma 3.1 implies $D_{m-1}$ must
contribute a color. Thus,
$c(\delta^{\prime})\not\in\\{c(\gamma^{\prime}),c(\beta)\\}$, contradicting
that $c$ is rainbow-free.

In either case, a contradiction is obtained, so $a_{1}=1$ or $t_{1}=1$, that
is, $\alpha=(1,2)$ or $\delta=(1,2)$.

Since $c(\alpha)=c(\delta)$, without loss of generality, suppose
$\alpha=(1,2)$. Now, assume, for the sake of contradiction, that
$\frac{m}{2}+1\leq s_{3}$. Define $\rho=(s_{3}-1,s_{3}-2)$ so that
$\alpha+\rho=(s_{3},s_{3})$, and $c(\rho)\in\\{c(\alpha),3\\}$. Since $\rho\in
D_{m-1}$, Lemmas 2.7 and 3.1 imply that $c(\rho)=3$. Lemma 3.1 further implies
that $D_{m-1}$ must contribute a color, say $D_{m-1}$ contributes $c(\xi)$ for
some $\xi=(e_{1},e_{2})\in D_{m-1}$. If $e_{1}<s_{3}-1$, then there exists
some $\kappa=(k,k)\in D_{m}$ such that $k<s_{3}$ and $\xi+\kappa=\rho$, a
rainbow solution. Otherwise, suppose $s_{3}-1<e_{1}$. Then there exists some
$\kappa=(k,k)\in D_{m}$ such that $\rho+\kappa=\xi$. Recall $e_{1}\leq m$ and
$\frac{m}{2}+1\leq s_{3}$, so

$k=e_{1}-(s_{3}-1)\leq m-s_{3}+1\leq(2s_{3}-2)-s_{3}+1<s_{3}.$

Thus, $\rho+\kappa=\xi$ is a rainbow solution. Both cases contradict that $c$
is rainbow-free.

Now consider when $s_{3}<\frac{m}{2}+1$. Lemma 2.2 implies $4\leq s_{3}$ so
$7\leq m\leq n$. Note that if $\chi=(x_{1},x_{2})\in D_{m+3}$ is such that
$2\leq x_{1}$, then there exists a jump from $\alpha$ to $\chi$ implying that
$c(\chi)\in c(D_{m})$. Since $D_{m+3}$ must contribute a color and the only
way it can contribute is if $x_{1}=1$, $D_{m+3}$ must contribute $c((1,4))$.
If $5\leq b_{2}$ (and $3\leq b_{1}$), then there is a jump from $(1,4)$ to
$\beta$. So, there exists some $\delta^{\prime\prime}\in D_{m-1}$ with
$c(\delta^{\prime\prime})\in\\{c((1,4)),c(\beta)\\}$, which is a contradiction
by Lemmas 2.7 and 3.1. Thus $b_{2}\in\\{3,4\\}$ but if $b_{2}=3$ there is not
a jump from $\alpha$ to $\beta$ so $\beta=(2,4)$. Finally,
$\alpha+\beta=(3,6)$. So, $c(3,6)\in\\{c(\alpha),c(\beta)\\}$, but $(3,6)\in
D_{m+3}$, which is a contradiction by Lemmas 2.7 and 3.1 . Therefore,
contradictions are obtained in every situation when $a=m+1$ and $b=m+2$.

The case when $a=m-1$ and $b=m-2$ is very similar. Essentially, reflect the
coordinates and diagonals from the argument above across the main diagonal.
The analysis forces $\alpha=(2,1)$ or $\delta=(2,1)$ and
$\rho=(s_{3}-2,s_{3}-1)$ is considered. However, the cases at this point
differ slightly. Instead of scrutinizing $\frac{m}{2}+1\leq s_{3}$ and
$s_{3}<\frac{m}{2}+1$ the cases that are considered are $\frac{m+1}{2}+1\leq
s_{3}$ and $s_{3}<\frac{m+1}{2}+1$. In any event, contradictions are
established in all situations so there are no jumps from $\alpha$ to $\beta$
with $c(\alpha),c(\beta)\notin c(D_{m})$ and $c(\alpha)\neq c(\beta)$. ∎

Lemma 3.3 bounds $s_{3}$ which in turn bounds $s_{2}$ in the proof of Theorem
3.4.

######  Lemma 3.3.

Suppose $c$ is a exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$ and $|c(D_{m})|=3$. If $i,j<s_{3}$, then
$c((i,j))\in c(D_{m})$.

###### Proof.

If $(i,j)\in D_{m}$, then $c((i,j))\in c(D_{m})$. So, suppose $(i,j)\in
D_{k}$, with $k\neq m$, and assume, for the sake of contradiction, that
$c((i,j))\notin c(D_{m})$. By Lemma 3.1, $D_{k}$ contributes $c((i,j))$.
Define $\alpha\in D_{a}$ so that $(i,j)+\alpha=(s_{3},s_{3})$ so
$c(\alpha)\in\\{c((i,j)),3$}. Lemma 2.15 implies $\alpha$ and $(i,j)$ are in
different diagonals, and Lemma 3.1 gives $c(\alpha)\neq c((i,j))$. Thus,
$c(\alpha)=3$.

Let $\beta=(b_{1},b_{2})\in D_{a}$ be distinct from $\alpha$. It will be shown
$c(\beta)\in c(D_{m})$. First, suppose there exists a $\gamma=(g_{1},g_{2})\in
D_{m}$ such that $\alpha+\gamma=\beta$. If $g_{1}<s_{3}$, then
$c(\gamma)\in\\{1,2\\}$. So, $c(\gamma)\neq c(\alpha)$ implying $c(\beta)\in
c(D_{m})$. If $s_{3}\leq g_{1}$, then $s_{3}\leq g_{2}$ implying $i<s_{3}\leq
g_{1}<b_{1}$ and $j<s_{3}\leq g_{2}<b_{2}$. So there is a jump from $(i,j)$ to
$\beta$, and Lemma 3.2 implies $c(\beta)\in c(D_{m})$.

Otherwise, suppose $\beta+\gamma=\alpha$. Then $g_{1}<s_{3}$, so
$c(\gamma)\in\\{1,2\\}$ which implies $c(\alpha)\neq c(\gamma)$ and
$c(\beta)\in c(D_{m})$. Thus, $c(D_{a})\setminus c(D_{m})=\emptyset$,
contradicting Lemma 3.1. Therefore, $c((i,j))\in c(D_{m})$. ∎

Lemma 3.4 gives that there are no rainbow-free $(m+n+1)$-colorings of $m\times
n$ with no more than $3$ colors in the main diagonal. Assuming that there is
such a coloring, this proof shows that there must exist a vertical and
horizontal pair that intersect $W$. This gives a contributing disjoint corner,
which contradicts Lemma 2.16.

######  Theorem 3.4.

If $c$ is an exact $(m+n+1)$-coloring of $[m]\times[n]$ with $3\leq m\leq n$
and $|c(D_{m})|\leq 3$, then $[m]\times[n]$ contains a rainbow solution to
$eq$.

###### Proof.

Assume, for the sake of contradiction, that $c$ is rainbow-free. Then
Corollary 2.9 implies $|c(D_{m})|=3$. Note Lemma 3.1 implies every off-
diagonal is a contributing diagonal. In particular, $D_{m-1}$ and $D_{m-2}$
contribute a color. Suppose for some $\alpha=(a_{1},a_{1}-1)\in D_{m-1}$,
$D_{m-1}$ contributes $c(\alpha)$ and for some $\beta=(b_{1},b_{1}-2)\in
D_{m-2}$, $D_{m-2}$ contributes $c(\beta)$. Thus, $P=\\{\alpha,\beta\\}$ is a
consecutive contributing pair of elements and Lemma 3.2 indicates $P$ is a
vertical or horizontal pair. Further, Lemma 3.3 implies that $s_{3}\leq
a_{1},b_{1}$. Note that $2\leq s_{2}\leq\frac{s_{3}}{2}\leq\frac{a_{1}}{2}$
with the middle inequality being a result of Lemma 2.2. Continuing,

$s_{2}\leq\frac{a_{1}}{2}=a_{1}-\frac{a_{1}}{2}<a_{1}-1<a_{1}.$

So, $\alpha=(a_{1},a_{1}-1)\in W_{2}$ and $P$ intersects $W$. A similar
argument indicates a vertical or horizontal pair, call it $P^{\prime}$, exists
and intersects $D_{m+1}$, $D_{m+2}$ and $W_{2}$.

Assume, for the sake of contradiction, that $P$ is a vertical pair. Then
$a_{1}-1=b_{1}-2$. Define $K$ to be the minimum $k$ such that $D_{k}$
contributes the color of an element of the $a_{1}-1$ column. More precisely,

$K=\min\\{k:D_{k}\text{ contributes }c((x,a_{1}-1))\text{ for some $x$}\\}.$

Notice that $K$ exists and $K\leq m-2$. By construction, $D_{K}$ contributes
$c((x,a_{1}-1))$ for $x=m-K+a_{1}-1$.

By Lemmas 3.1 and 3.2, $D_{K-1}$ must contribute $c((x+1,a_{1}-1))$ or
$c((x,a_{1}-2))$. By the minimality of $K$, $D_{K-1}$ must contribute
$c((x,a_{1}-2))$. This implies $P_{1}=\\{(x,a_{1}-2),(x,a_{1}-1)\\}$ is a
horizontal pair. Now, since $s_{2}<a_{1}-1<m-K+a_{1}-1=x$, so $P_{1}$
intersects $W_{2}$. However, now $P_{1}$ and $P^{\prime}$ or $P$ and
$P^{\prime}$ are contributing disjoint corners which contradicts Lemma 2.16.
Thus, $P$ must be a horizontal pair.

Note that $D_{m+1}$ must contribute $c(\gamma)$ for some
$\gamma=(g_{1},g_{1}+1)\in D_{m+1}$. Then $s_{3}\leq g_{1}+1$ by Lemma 3.3.
Now, define $L$ to be the maximum $\ell$ such that $D_{\ell}$ contributes the
color of an element of the $g_{1}$ row. Specifically,

$L=\max\\{\ell:D_{\ell}\text{ contributes }c((g_{1},y))\text{ for some
$y$}\\}.$

Again, notice that $m+1\leq L$. So, $D_{L}$ contributes $c((g_{1},y))$ for
$y=L-m+g_{1}$.

Then Lemma 3.2 and the maximality of $L$ implies that $D_{L+1}$ must
contribute $c((g_{1}-1,y))$. Then $P_{2}=\\{(g_{1},y),(g_{1}-1,y)\\}$ is a
vertical pair that intersects $W_{2}$, using a similar argument as before.
Finally, since $s_{2}\geq 2$, Lemma 2.2 implies $s_{2}<s_{3}-1\leq
g_{1}<L-m+g_{1}=y$. So, $(g_{1},y)\in W_{2}$ implying that $P_{2}$ and $P$
form a contributing disjoint corner, which contradicts Lemma 2.16. Therefore,
$[m]\times[n]$ contains a rainbow solution. ∎

##  4 Four or More Colors in Main Diagonal

The main result of Section 3 states that every exact $(m+n+1)$-coloring of
$[m]\times[n]$ will contain a rainbow solution to $eq$ if there are three
colors in the main diagonal. Section 4 culminates with Theorem 4.9 which shows
that if an exact $(m+n+1)$-coloring of $[m]\times[n]$ contains a jump, then a
rainbow solution to $eq$ exists. To start, a useful set of diagonals is
defined.

For each $\delta\in[m]\times[n]$ define the set of off-diagonals

$\mathbb{D}_{\delta}:=\\{D_{g}\neq D_{m}\,:\,\text{for all $\gamma\in D_{g}$,
either $\gamma+\delta$ or $\gamma-\delta$ is in $[m]\times[n]$}\\}.$

Lemma 4.1 gives an upper bound for the number of colors that can exist in
$[m]\times[n]$ that do not appear in the main diagonal. The upper bound is
written with respect to the cardinality of some $\mathbb{D}_{\delta}$ with
$c(\delta)\notin c(D_{m})$. The proof proceeds with two cases, when there are
at least $\frac{|\mathbb{D}_{\delta}|}{3}$ non-contributing diagonals in
$\mathbb{D}_{\delta}$ and when there are less than
$\frac{|\mathbb{D}_{\delta}|}{3}$ non-contributing diagonals in
$\mathbb{D}_{\delta}$. The former case is immediate. In the latter case, it is
shown that there are at least $\frac{2|\mathbb{D}_{\delta}|}{3}-3$
contributing diagonals that are each associated with some non-contributing
diagonal and at most two of these contributing diagonals are associated with
the same non-contributing diagonal. This leads to the conclusion that there
are at least $\frac{|\mathbb{D}_{\delta}|}{3}-\frac{3}{2}$ non-contributing
diagonals in $[m]\times[n]$. Subtracting this from the total number of off-
diagonals gives the upper bound.

######  Lemma 4.1.

Let $c$ be an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$. For each $\delta$ such that $c(\delta)\notin
c(D_{m})$,

$|c([m]\times[n])\setminus c(D_{m})|\leq
m+n-\frac{1}{2}-\frac{|\mathbb{D}_{\delta}|}{3}.$

###### Proof.

Assume $\delta\in D_{t}$ and suppose there are $k$ non-contributing diagonals
in $\mathbb{D}_{\delta}$, and assume $k\geq\frac{|\mathbb{D}_{\delta}|}{3}$.
Since there are $m+n-2$ off-diagonals and at least
$\frac{|\mathbb{D}_{\delta}|}{3}$ are non-contributing, it follows that

$\left|c([m]\times[n])\setminus c(D_{m})\right|\leq
m+n-2-\frac{|\mathbb{D}_{\delta}|}{3}<m+n-\frac{1}{2}-\frac{|\mathbb{D}_{\delta}|}{3}.$

On the other hand, suppose $k<\frac{|\mathbb{D}_{\delta}|}{3}$. This implies
there are at least $\frac{2|\mathbb{D}_{\delta}|}{3}$ contributing diagonals
in $\mathbb{D}_{\delta}$. Note that at most one of these contributing
diagonals contains $c(\delta)$. Define $D_{x}$ to be the diagonal in
$[m]\times[n]$ that contributes $c(\delta)$. This means there are at least
$\frac{2|\mathbb{D}_{\delta}|}{3}-1$ contributing diagonals in
$\mathbb{D}_{\delta}$ that do not contain $c(\delta)$. Let $D_{g}$ be one of
those diagonals. Then there exists $\gamma\in D_{g}$ such that $D_{g}$
contributes $c(\gamma)$ with $c(\gamma)\notin c(D_{m})\cup\\{c(\delta)\\}$.
Since $D_{g}\in\mathbb{D}_{\delta}$, either $\gamma+\delta\in[m]\times[n]$ or
$\gamma-\delta\in[m]\times[n]$ implying either
$\\{\gamma,\delta,\gamma+\alpha\\}$ or $\\{\delta,\gamma-\delta,\gamma\\}$ is
a solution in $[m]\times[n]$. Specifically, $\gamma+\delta\in D_{g+t-m}$ and
$\gamma-\delta\in D_{g-t+m}$ by Lemma 2.15.

Since $c$ is rainbow-free, either $c(\gamma+\delta)$ or $c(\gamma-\delta)$ is
in $\\{c(\gamma),c(\delta)\\}$. This implies either $c(D_{g+t-m})$ or
$c(D_{g-t+m})$ contains $c(\gamma)$ or $c(\delta)$. If $D_{g+t-m}$ or
$D_{g-t+m}$ contains $c(\gamma)$, then, since $D_{g}$ contributes $c(\gamma)$,
either $D_{g+t-m}$ or $D_{g-t+m}$ is non-contributing. If $D_{g+t-m}$ or
$D_{g-t+m}$ contains $c(\delta)$, then $D_{g+t-m}$ or $D_{g-t+m}$ is
contributing if and only if $D_{g+t-m}=D_{x}$ or $D_{g-t+m}=D_{x}$. This
analysis shows that if $D_{g}\in\\{D_{x+t-m},D_{x-t+m}\\}$, then $D_{g}$ does
not necessarily correspond to a non-contributing diagonal. Applying similar
analysis to $D_{x}$ indicates that if $D_{x}\in\mathbb{D}_{\delta}$, then
$D_{x}$ does not necessarily correspond to a non-contributing diagonal.

Define $G$ to be the set of all contributing diagonals in
$\mathbb{D}_{\delta}\setminus\\{D_{x},D_{x+t-m},D_{x-t+m}\\}$. Thus, each
$D_{g}\in G$ corresponds to at least one non-contributing off-diagonal, namely
$D_{g+t-m}$ or $D_{g-t+m}$, and

$\frac{2|\mathbb{D}_{\delta}|}{3}-3\leq|G|.$

If $G$ is empty, then $|\mathbb{D}_{\delta}|\leq 9/2$ so

$\displaystyle\left|c([m]\times[n])\setminus c(D_{m})\right|$
$\displaystyle\leq m+n-2$ $\displaystyle\leq
m+n-\frac{1}{2}-\frac{|\mathbb{D}_{\delta}|}{3}.$

So assume $G$ is non-empty and let $D_{g}\in G$ so that $D_{g+t-m}$ or
$D_{g-t+m}$ is non-contributing. Without loss of generality, suppose
$D_{g+t-m}$ is non-contributing. For the sake of contradiction, suppose
$D_{h},D_{h^{\prime}}\in G\setminus\\{D_{g}\\}$ are distinct with
$D_{g+t-m}\in\\{D_{h+t-m},D_{h-t+m}\\}\cap\\{D_{h^{\prime}+t-m},D_{h^{\prime}-t+m}\\}$.
Since $g\notin\\{h,h^{\prime}\\}$, it must be that $g+t-m=h-t+m$ and
$g+t-m=h^{\prime}-t+m$ implying $h=h^{\prime}$, a contradiction. So, there is
at most one diagonal $D_{h}$ in $G$ such that
$D_{g+t-m}\in\\{D_{h+t-m},D_{h-t+m}\\}$. In other words, at most two diagonals
in $G$ correspond to the same non-contributing off-diagonal.

Since $D_{g}\in G$ was arbitrary, it can be concluded that at least
$\frac{|G|}{2}$ diagonals are non-contributing. Thus,

$\displaystyle\left|c([m]\times[n])\setminus c(D_{m})\right|$
$\displaystyle\leq m+n-2-\frac{|G|}{2}$ $\displaystyle\leq
m+n-2-\frac{\frac{2|\mathbb{D}_{\delta}|}{3}-3}{2}$
$\displaystyle=m+n-\frac{1}{2}-\frac{|\mathbb{D}_{\delta}|}{3}.$

∎

As stated, the main goal of this section is to show that a jump with
distinctly colored elements yields a rainbow solution. Propositions 4.2 and
4.6 give lower and upper bounds, respectively, on the jump distance which
leaves only a few cases to analyze.

######  Proposition 4.2.

Let $c$ be an exact, rainbow free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$. If there exists an $\delta=(d_{1},d_{2})$ such that
$c(\delta)\notin c(D_{m})$, then

$\frac{4m+9-6\left\lfloor\log_{2}(m)+1\right\rfloor}{4}\leq d_{1}+d_{2}.$

###### Proof.

Define

${S}_{\delta}:=\\{\gamma\in[m]\times[n]\,|\,\gamma+\delta,\gamma-\delta\notin[m]\times[n]\\}.$

Notice $\delta^{\prime}=(m-d_{1}+1,d_{2})\in D_{d_{1}+d_{2}-1}$ and
$\delta^{\prime}\pm\delta\notin[m]\times[n]$ (see Figure 3). Since there are
$m+n-2$ off-diagonals and $S_{\delta}$ intersects $2(d_{1}+d_{2}-1)$
diagonals, it follows
$|\mathbb{D}_{\delta}|=m+n-2-2(d_{1}+d_{2}-1)=m+n-2d_{1}-2d_{2}$. If
$S_{\delta}$ intersects $D_{m}$, then
$|\mathbb{D}_{\delta}|=m+n-2d_{1}-2d_{2}+1$. So, $|\mathbb{D}_{\delta}|\geq
m+n-2d_{1}-2d_{2}.$ Therefore, Lemma 4.1 implies that

$\begin{split}|c([m]\times[n])\setminus c(D_{m})|&\leq
m+n-\frac{1}{2}-\frac{|\mathbb{D}_{\delta}|}{3}\\\ &\leq
m+n-\frac{1}{2}-\frac{m+n-2d_{1}-2d_{2}}{3}\\\
&=\frac{4m+4n-3+4d_{1}+4d_{2}}{6}.\end{split}$ (5)

Because $c$ is a rainbow-free, Theorem 2.4 implies
$|c(D_{m})|\leq\left\lfloor\log_{2}(m)+1\right\rfloor$. Further, $c$ is an
exact $m+n+1$-coloring, so

$m+n+1-\left\lfloor\log_{2}(m)+1\right\rfloor\leq|c([m]\times[n])\setminus
c(D_{m})|.$ (6)

Inequalities (5) and (6) give

$m+n+1-\left\lfloor\log_{2}(m)+1\right\rfloor\leq|c([m]\times[n])\setminus
c(D_{m})|\leq\frac{4m+4n-3+4d_{1}+4d_{2}}{6}.$

Isolating $d_{1}+d_{2}$ and using $m\leq n$ gives

$\frac{4m+9-6\left\lfloor\log_{2}(m)+1\right\rfloor}{4}\leq\frac{2m+2n+9-6\left\lfloor\log_{2}(m)+1\right\rfloor}{4}\leq
d_{1}+d_{2}.$ (7)

∎

$S_{\delta}$$S_{\delta}$$\delta$$\delta^{\prime}$$\mathbb{D}_{\delta}$ Figure
3: A visualization of $\delta$, $\delta^{\prime}$ and $S_{\delta}$ (in red)
and $\mathbb{D}_{\delta}$ (in cyan) from Proposition 4.2.

Lemmas 4.3, 4.4 and 4.5 support Proposition 4.6. The assumptions for all of
these results are that there is a jump from $\alpha=(a_{1},a_{2})$ to
$\beta=(b_{1},b_{2})$, $\alpha\in D_{a}$ and $\beta\in D_{b}$,
$c(\alpha),c(\beta)\notin c(D_{m})$ and $c(\alpha)\neq c(\beta)$. Also,
$\alpha+(d_{1},d_{2})=\beta$. The goal is to find a relationship between the
jump distance, $d_{1}+d_{2}$, and the number of contributing diagonals. The
main challenge arises during the analysis of the diagonals that surround
$D_{a}$ and $D_{b}$. Technically, this set of surrounding diagonals is $S$
which was defined by (1) and visualized in Figure 1. During the analysis of
$S$ many iterations of jumps need to be considered. For example, if $\gamma$
is an element in one of the diagonals of $S$ then there must be a jump from
$\alpha$ to $\gamma$ (or from $\gamma$ to $\beta$) which introduces another
element $\zeta$ where $\alpha+\zeta=\gamma$ (or $\gamma+\zeta=\beta$). Lemma
4.3 starts investigating where $\zeta$ could be in the $\alpha+\zeta=\gamma$
case and Lemma 4.4 starts investigating where $\zeta$ could be in the
$\gamma+\zeta=\beta$ case. Lemma 4.5 adds more clarification about where the
$\zeta$ elements can be.

######  Lemma 4.3.

Let $c$ be an exact, rainbow free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$, and suppose there is a jump from $\alpha\in D_{a}$
to $\beta\in D_{b}$ such that $\alpha+\delta=\beta$ for some $\delta\in
D_{t}$. If $c(\alpha),c(\beta)\notin c(D_{m})$ and $c(\alpha)\neq c(\beta)$,
then there is at most one diagonal $D_{g}$ that contains an element $\gamma$
with $c(\gamma)\notin c(D_{m}\cup\\{\alpha,\beta\\})$ such that
$\alpha+\zeta=\gamma$ for some $\zeta\in D_{z}$ with $z\in\\{a,b,t,m,g\\}$.
Moreover, if such a $D_{g}$ exists, then $z=a$.

###### Proof.

Assume there exist diagonals $D_{g}$ and $D_{g^{\prime}}$ such that for some
$\gamma\in D_{g}$ and $\gamma^{\prime}\in D_{g^{\prime}}$,
$c(\gamma),c(\gamma^{\prime})\notin c(D_{m}\cup\\{\alpha,\beta\\})$ and there
is a $\zeta\in D_{z}$ and $\zeta^{\prime}\in D_{z^{\prime}}$ such that
$\alpha+\zeta=\gamma$ and $\alpha+\zeta^{\prime}=\gamma^{\prime}$ with
$z\in\\{a,b,t,m,g\\}$ and $z^{\prime}\in\\{a,b,t,m,g^{\prime}\\}$.

Since $a\neq m$, it follows that $z\neq g$ and $z^{\prime}\neq g^{\prime}$, so
$z,z^{\prime}\in\\{a,b,t,m\\}$. Additionally, $c(\gamma)\neq c(\alpha)$ and
$c(\gamma^{\prime})\neq c(\alpha)$ imply that
$c(\zeta)\in\\{c(\alpha),c(\gamma)\\}$ and
$c(\zeta^{\prime})\in\\{c(\alpha),c(\gamma^{\prime})\\}$. Thus,
$z,z^{\prime}\notin\\{m,b\\}$. Since $c(\gamma),c(\gamma^{\prime})\notin
c(D_{m}\cup\\{\alpha,\beta\\})$, Lemma 2.7 implies $g\neq b$ and
$g^{\prime}\neq b$. Thus, by Lemma 2.15, $z\neq t$ and $z^{\prime}\neq t$. So,
it must be the case that $z=z^{\prime}=a$. Finally, Lemma 2.15 gives that
$g=g^{\prime}=2a-m$, that is $D_{g}$ is unique. ∎

######  Lemma 4.4.

Let $c$ be an exact, rainbow free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$, and suppose there is a jump from $\alpha\in D_{a}$
to $\beta\in D_{b}$ such that $\alpha+\delta=\beta$ for some $\delta\in
D_{t}$. If $c(\alpha),c(\beta)\notin c(D_{m})$ and $c(\alpha)\neq c(\beta)$,
then there is at most one diagonal $D_{g}$ that contains an element $\gamma$
with $c(\gamma)\notin c(D_{m}\cup\\{\alpha,\beta\\})$ such that
$\gamma+\zeta=\beta$ for some $\zeta\in D_{z}$ with $z\in\\{a,b,t,m,g\\}$.
Moreover, if such a $D_{g}$ exists, then $z=g$.

###### Proof.

Assume there exist diagonals $D_{g}$ and $D_{g^{\prime}}$ such that for some
$\gamma\in D_{g}$ and $\gamma^{\prime}\in D_{g^{\prime}}$,
$c(\gamma),c(\gamma^{\prime})\notin c(D_{m}\cup\\{\alpha,\beta\\})$ and there
is a $\zeta\in D_{z}$ and $\zeta^{\prime}\in D_{z^{\prime}}$ such that
$\gamma+\zeta=\beta$ and $\gamma^{\prime}+\zeta^{\prime}=\beta$ with
$z\in\\{a,b,t,m,g\\}$ and $z^{\prime}\in\\{a,b,t,m,g^{\prime}\\}$.

Since $c(\gamma)\neq c(\beta)$ and $c(\gamma^{\prime})\neq c(\beta)$, it
follows that $c(\zeta)\in\\{c(\beta),c(\gamma)\\}$ and
$c(\zeta^{\prime})\in\\{c(\beta),c(\gamma^{\prime})\\}$. Thus,
$z,z^{\prime}\notin\\{a,m\\}$. Also, $g\neq m$ and $g^{\prime}\neq m$ imply
that $z\neq b$ and $z^{\prime}\neq b$. Since
$c(\gamma),c(\gamma^{\prime})\notin c(D_{m}\cup\\{\alpha,\beta\\})$, Lemma 2.7
implies $g\neq a$ and $g^{\prime}\neq a$. Thus, by Lemma 2.15, $z\neq t$ and
$z^{\prime}\neq t$. Therefore, $z=g$ and $z^{\prime}=g^{\prime}$. Now, by
Lemma 2.15, $b=z+g-m=2g-m$ and $b=z^{\prime}+g^{\prime}-m=2g^{\prime}-m$. So,
$g=g^{\prime}$, showing $g$ is unique. ∎

######  Lemma 4.5.

Let $c$ be an exact, rainbow free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$ and suppose there is an element $\alpha\in D_{a}$
and an element $\beta\in D_{b}$ such that $c(\alpha)\neq c(\beta)$, and
$c(\alpha),c(\beta)\notin c(D_{m})$. Let

$S^{\prime}\subseteq\\{D_{x}\leavevmode\nobreak\ |\leavevmode\nobreak\
c(D_{x})\backslash c(D_{m}\cup D_{a}\cup D_{b})\neq\emptyset\\}$

and

$G:=\\{D_{x}\in S^{\prime}\leavevmode\nobreak\ |\leavevmode\nobreak\ \text{if
$c(D_{x})\backslash c(D_{m})=c(D_{y})\backslash c(D_{m})$ for some $D_{y}\in
S^{\prime}$, then $x\leq y$}\\}.$

If $D_{g_{i}}\in G$ and $\gamma_{i}\in D_{g_{i}}$ with $c(\gamma_{i})\notin
c(D_{m}\cup\\{\alpha,\beta\\})$ and there is a corresponding $\zeta_{i}\in
D_{z_{i}}$ such that either $\alpha+\zeta_{i}=\gamma_{i}$ or
$\gamma_{i}+\zeta_{i}=\beta$, then $D_{z_{i}}\notin
G\setminus\\{D_{g_{i}}\\}$. Moreover, if $i\neq j$, then $z_{i}\neq z_{j}$.

###### Proof.

For the sake of contradiction, suppose $D_{z_{i}}\in
G\setminus\\{D_{g_{i}}\\}$. By definition of $G$ there is a $\rho\in
D_{z_{i}}$ such that $c(\rho)\notin c(D_{m}\cup\\{\alpha,\beta\\})$. Since
$z_{i}\neq g_{i}$, it follows that $c(\rho)\neq c(\gamma_{i})$. Further,
$\alpha+\zeta_{i}=\gamma_{i}$ or $\gamma_{i}+\zeta_{i}=\beta$ implies
$c(\zeta_{i})\in c(\\{\alpha,\gamma_{i},\beta\\})$. Thus, $c(\zeta_{i})\neq
c(\rho)$, and $c(\zeta_{i}),c(\rho)\notin c(D_{m})$, which contradicts Lemma
2.7. Therefore, $D_{zi}\notin G\setminus\\{D_{gi}\\}$.

Let $i\neq j$, $\gamma_{j}\in D_{g_{j}}$ with $c(\gamma_{j})\notin
c(D_{m}\cup\\{\alpha,\beta\\})$ have corresponding $\zeta_{j}\in D_{z_{j}}$.
If $\alpha+\zeta_{i}=\gamma_{i}$ and $\alpha+\zeta_{j}=\gamma_{j}$, or
$\gamma_{i}+\zeta_{i}=\beta$ and $\gamma_{j}+\zeta_{j}=\beta$, then $g_{i}\neq
g_{j}$ and Lemma 2.15 imply $z_{i}\neq z_{j}$. On the other hand, without loss
of generality, if $\alpha+\zeta_{i}=\gamma_{i}$ and
$\gamma_{j}+\zeta_{j}=\beta$, then
$c(\zeta_{i})\in\\{c(\gamma_{i}),c(\alpha)\\}$ and
$c(\zeta_{j})\in\\{c(\gamma_{j}),c(\beta)\\}$. This implies $c(\zeta_{i})\neq
c(\zeta_{j})$ so Lemma 2.7 implies $z_{i}\neq z_{j}$. ∎

######  Proposition 4.6.

Let $c$ be an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$. If $\alpha+(d_{1},d_{2})=\beta$ corresponds to a
jump from $\alpha$ to $\beta$ where $c(\alpha),c(\beta)\notin c(D_{m})$ and
$c(\alpha)\neq c(\beta)$, then $d_{1}+d_{2}\leq 2\log_{2}(m)+1$.

###### Proof.

Let $\alpha=(a_{1},a_{2})\in D_{a}$, $\beta=(b_{1},b_{2})\in D_{b}$, and
$\delta=(d_{1},d_{2})\in D_{t}$. Since $c$ is rainbow-free,
$c(\delta)\in\\{c(\alpha),c(\beta)\\}$. Define $S$ as in (1). By Lemmas 2.14
and 2.13, every element of every diagonal in $S$ has a solution with $\alpha$
or $\beta$. In particular, if $\gamma$ is such an element, then there is
either a jump from $\alpha$ to $\gamma$ or from $\gamma$ to $\beta$.

Further, define

$S^{\prime}:=\\{D_{x}\in S\leavevmode\nobreak\ |\leavevmode\nobreak\
c(D_{x})\backslash c(D_{m}\cup D_{a}\cup D_{b})\neq\emptyset\\},$

and

$G:=\\{D_{x}\in S^{\prime}\leavevmode\nobreak\ |\leavevmode\nobreak\ \text{if
$c(D_{x})\backslash c(D_{m})=c(D_{y})\backslash c(D_{m})$ for some $D_{y}\in
S^{\prime}$, then $x\leq y$}\\}.$

Also, define

$T:=\\{D_{x}\in[m]\times[n]\leavevmode\nobreak\ |\leavevmode\nobreak\
D_{x}\notin S\cup\\{D_{m},D_{a},D_{b}\\}\\},$

and

$T^{\prime}:=\left\\{D_{x}\in T\leavevmode\nobreak\ |\leavevmode\nobreak\
c(D_{x})\not\subseteq c\left(D_{m}\cup D_{a}\cup D_{b}\cup\bigcup_{D_{s}\in
S}D_{s}\right)\right\\}.$

Accounting for the facts that $D_{a},D_{b},D_{m}\notin S$ and
$\delta=\beta-\alpha$,

$|S|\geq(m+b_{2}-a_{1})-(m+a_{2}-b_{1})-1-3=d_{1}+d_{2}-4.$

Suppose $|G|=k$ and reindex $G=\\{D_{g_{1}},\ldots,D_{g_{k}}\\}$. Note that
for each $D_{g_{i}}\in G$ there exists $\gamma_{i}\in D_{g_{i}}$ with
$c(\gamma_{i})\notin c(D_{m}\cup\\{\alpha,\beta\\})$ and $c(\gamma_{i})\neq
c(\gamma_{j})$ when $i\neq j$. In addition, as $D_{g_{i}}\in S$, there exists
a diagonal $D_{z_{i}}$ with $\zeta_{i}\in D_{z_{i}}$ such that
$\alpha+\zeta_{i}=\gamma_{i}$ or $\gamma_{i}+\zeta_{i}=\beta$. Define
$Z:=\\{D_{z_{i}}\leavevmode\nobreak\ |\leavevmode\nobreak\ \zeta_{i}\in
D_{z_{i}}\text{ for }1\leq i\leq k\\}$. By Lemmas 4.3 and 4.4, at least $k-2$
diagonals $D_{z_{i}}$ of $Z$ are not in
$\\{D_{a},D_{b},D_{t},D_{m},D_{g_{i}}\\}$. Define

$Z^{\prime}:=\begin{cases}\big{\\{}D_{z_{i}}\in Z\leavevmode\nobreak\
|\leavevmode\nobreak\
D_{z_{i}}\notin\\{D_{a},D_{b},D_{t},D_{m},D_{g_{i}}\\}\big{\\}}&\text{if
$a=t$,}\\\ \big{\\{}D_{z_{i}}\in Z\leavevmode\nobreak\ |\leavevmode\nobreak\
D_{z_{i}}\notin\\{D_{a},D_{b},D_{t},D_{m},D_{g_{i}}\\}\big{\\}}\cup\\{D_{t}\\}&\text{if
$a\neq t$.}\end{cases}$

For all $D_{z_{i}},D_{z_{j}}\in Z\cap Z^{\prime}$, Lemma 4.5 implies that
$D_{z_{i}}\notin G$ and $z_{i}\neq z_{j}$ when $i\neq j$. It follows that

$Z^{\prime}=\begin{cases}\big{\\{}D_{z_{i}}\in Z\leavevmode\nobreak\
|\leavevmode\nobreak\ D_{z_{i}}\notin\\{D_{a},D_{b},D_{t},D_{m}\\}\cup
G\big{\\}}&\text{if $a=t$,}\\\ \big{\\{}D_{z_{i}}\in Z\leavevmode\nobreak\
|\leavevmode\nobreak\ D_{z_{i}}\notin\\{D_{a},D_{b},D_{t},D_{m}\\}\cup
G\big{\\}}\cup\\{D_{t}\\}&\text{if $a\neq t$.}\end{cases}$

Lemmas 4.3 and 4.4 imply $k-1\leq|Z^{\prime}|$.

Note that $c(\zeta_{i})\in\\{c(\alpha),c(\beta),c(\gamma_{i})\\}$, so
$c(\zeta_{i})\notin c(D_{m})$ and $|c(D_{z_{i}})\setminus c(D_{m}\cup
D_{a}\cup D_{b}\cup D_{g_{i}})|=0$ by Lemma 2.7. Also,
$c(\delta)\in\\{c(\alpha),c(\beta)\\}$, so $|c(D_{t})\setminus c(D_{m}\cup
D_{a}\cup D_{b}|=0$. Thus,

$c\left(\bigcup_{D_{x}\in Z^{\prime}}D_{x}\right)\subseteq c\left(D_{m}\cup
D_{a}\cup D_{b}\cup\bigcup_{D_{g_{i}}\in G}D_{g_{i}}\right).$

Note that by definition, for all $D_{x}\in Z^{\prime}$, $D_{x}\notin
G\cup\\{D_{a},D_{b},D_{m}\\}$, so $Z^{\prime}\subseteq(T\setminus
T^{\prime})\cup(S\setminus G)$.

If $k\leq\frac{|S|}{2}$, then there are at least $\frac{|S|}{2}$ off-diagonals
in $S\setminus G$. Therefore, there are at least $\frac{|S|}{2}$ off-diagonals
in $(T\setminus T^{\prime})\cup(S\setminus G)$. If $k\geq\frac{|S|+1}{2}$,
then $|Z^{\prime}|\geq k-1\geq\frac{|S|-1}{2}$. Since
$Z^{\prime}\subseteq(T\setminus T^{\prime})\cup(S\setminus G)$, there are at
least $\frac{|S|-1}{2}$ off-diagonals in $(T\setminus
T^{\prime})\cup(S\setminus G)$.

Recall, $|S|\geq d_{1}+d_{2}-4$. This implies there are at least

$\frac{d_{1}+d_{2}-5}{2}$

off-diagonals in $(T\setminus T^{\prime})\cup(S\setminus G)$.

Because there are a total of $m+n-2$ off-diagonals and Lemma 2.7 implies that
each off-diagonal can contain at most one color not in the main diagonal,
there are at most

$m+n-2-\frac{d_{1}+d_{2}-5}{2}$

colors in $c([m]\times[n])\backslash c(D_{m})$. Therefore, there are at least

$m+n+1-\left(m+n-2-\frac{d_{1}+d_{2}-5}{2}\right)=3+\frac{d_{1}+d_{2}-5}{2}$

colors in $c(D_{m})$. By Theorem 2.4,

$|c(D_{m})|\leq\log_{2}(m)+1,$

so

$3+\frac{d_{1}+d_{2}-5}{2}\leq\log_{2}(m)+1.$

Therefore,

$d_{1}+d_{2}\leq 2\log_{2}(m)+1.$

∎

Combining the inequalities in Propositions 4.2 and 4.6 gives the following
Corollary.

######  Corollary 4.7.

Let $c$ be an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $m\leq n$. If $11\leq m$ or $14\leq n$, then there are no jumps
between elements $\alpha$ and $\beta$ such that $c(\alpha),c(\beta)\notin
c(D_{m})$ and $c(\alpha)\neq c(\beta)$. Furthermore, when $8\leq m\leq 10$, it
follows that $5\leq d_{1}+d_{2}\leq 7$.

###### Proof.

Assume there is a jump from $\alpha$ to $\beta$. In particular,
$\alpha+(d_{1},d_{2})=\beta$. Then, the inequalities from Propositions 4.2 and
4.6 must be satisfied, so

$\frac{4m+9-6\left\lfloor\log_{2}(m)+1\right\rfloor}{4}\leq d_{1}+d_{2}\leq
2\log_{2}(m)+1.$ (8)

This can only happen if $m\leq 10$. Further, Inequality (7) implies $n\leq 13$
and if $8\leq m\leq 10$, Inequality (8) implies $5\leq d_{1}+d_{2}\leq 7$. ∎

Lemma 4.8 is used to generalize Corollary 4.7 into Theorem 4.9. The proof of
Lemma 4.8 uses analysis similar to the proof of Proposition 4.6 but the
additional constraint that $|c(D_{m})|=4$, deduced using Corollary 4.7, leads
to deeper case analysis.

######  Lemma 4.8.

Let $c$ be an exact, rainbow free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$, and suppose there is a jump from $\alpha\in D_{a}$
to $\beta\in D_{b}$ such that $\alpha+\delta=\beta$ for some
$\delta=(d_{1},d_{2})\in D_{t}$. If $c(\alpha),c(\beta)\notin c(D_{m})$ and
$c(\alpha)\neq c(\beta)$, then $2m-t=b$.

###### Proof.

Corollary 2.9 and Lemma 3.2 imply $4\leq|c(D_{m})|$. Lemma 2.5 and Corollary
4.7 further restrict to the situation to $8\leq m\leq 10$, $n\leq 13$, $5\leq
d_{1}+d_{2}\leq 7$, and $|c(D_{m})|=4$. For the sake of contradiction, assume
$2m-t\neq b$. First, note that if $2m-t=a$, then subtracting $m-t$ from both
sides gives $m=a+t-m$ and $a+t-m=b$ by Lemma 2.15 implying $m=b$, a
contradiction. Thus, $2m-t\notin\\{a,b\\}$.

Notice $d_{1}+d_{2}\leq 7$ and $8\leq s_{4}$ imply that
$\varsigma=(s_{4},s_{4})-\delta\in[m]\times[n]$ and more specifically,
$\varsigma\in D_{2m-t}$ by Lemma 2.15. It will be shown that one of
$D_{a},D_{b},D_{2m-t}$ is non-contributing. Note that
$\delta+\varsigma=(s_{4},s_{4})$ implies
$c(\varsigma)\in\\{c(\delta),4\\}\subset\\{c(\alpha),c(\beta),4\\}$. If
$c(\varsigma)\in\\{c(\alpha),c(\beta)\\}$, then at least one of
$D_{a},D_{b},D_{2m-t}$ is non-contributing. Otherwise, suppose
$c(\varsigma)=4$. It will be shown that $D_{2m-t}$ is non-contributing, the
desired result. So, let $\rho=(p_{1},p_{2})\in D_{2m-t}$. If
$p_{1}<s_{4}-d_{1}$, then there exists some $k<s_{4}$ such that
$\rho+(k,k)=\varsigma$ implying $c(\rho)\in c(D_{m})$. Second, suppose
$s_{4}-d_{1}<p_{1}<2s_{4}-d_{1}$. Then there exists some $k<s_{4}$ such that
$(k,k)+\varsigma=\rho$ implying $c(\rho)\in c(D_{m})$. Finally, suppose
$2s_{4}-d_{1}\leq p_{1}$ which means $2s_{4}-d_{2}\leq p_{2}$. Notice that
$p_{1}\leq m\leq 10$ and that $8\leq s_{4}$ by Corollary 2.3. So, $d_{1}\geq
2s_{4}-p_{1}\geq 16-10\geq 6$. But then $d_{1}+d_{2}\leq 7$ implies $d_{2}\leq
1$. So, $p_{2}\geq 2s_{4}-d_{2}\geq 16-1=15>n$. Thus, no such $\rho$ exists
proving that $c(D_{2m-t})\subseteq c(D_{m})$ implying that $D_{2m-t}$ is non-
contributing.

Thus, every diagonal $D_{k}$ with $k\notin\\{m,a,b,2m-t\\}$ must contribute a
color distinct from $c(\alpha)$ and $c(\beta)$. Consider $D_{t}$. Since
$\alpha+\delta=\beta$, it follows that $c(\delta)\in\\{c(\alpha),c(\beta)\\}$
and Lemma 2.7 implies $c(D_{t})\subseteq
c(D_{m})\cup\\{c(\alpha),c(\beta)\\}$. So, $D_{t}$ can’t contribute a color
distinct from $c(\alpha)$ and $c(\beta)$. Thus, $t\in\\{m,a,b,2m-t\\}$.
However, $a\neq b$ implies $t\neq m$ which implies $t\neq 2m-t$. Further
$a\neq m$ implies $t\neq b$. So, $t=a$.

Define $S$ as in (1) and note that

$|S|=\begin{cases}d_{1}+d_{2}-3&\text{if
$m\notin\\{D_{x}\,|\,m+a_{2}-b_{1}<x<m+b_{2}-a_{1}\\}$},\\\
d_{1}+d_{2}-4&\text{if
$m\in\\{D_{x}\,|\,m+a_{2}-b_{1}<x<m+b_{2}-a_{1}\\}$}.\end{cases}$

Since $5\leq d_{1}+d_{2}$, it follows that $1\leq|S|$. It is claimed that if
$D_{2m-t}\notin S$, then there exists some $D_{g}\in
S\backslash\\{D_{2m-t}\\}$. So assume $D_{2m-t}\in S$. By definition of $S$,
$m+a_{2}-b_{1}<2m-t<m+a_{1}-b_{2}$ which implies
$m+a_{2}-b_{1}<a+b-(2m-t)<m+a_{1}-b_{2}$. Thus, $D_{a+b-(2m-t)}\in
S\backslash\\{D_{2m-t}\\}$ because if $a+b-(2m-t)\in\\{a,b,m,2m-t\\}$, it can
be concluded that either $b=2m-t$ or $a=m$, both of which are contradictions.
Thus, there exists some $D_{g}\in S$ such that $g\neq 2m-t$.

Since $g\notin\\{m,a,b,2m-t\\}$, it follows that $D_{g}$ must contribute
$c(\gamma)$ for some $\gamma\in D_{g}$. By Lemmas 2.13 and 2.14, there exists
a $\zeta\in D_{z}$ such that $\alpha+\zeta=\gamma$ or $\gamma+\zeta=\beta$. In
either case, $c(\zeta)\in\\{c(\alpha),c(\beta),c(\gamma)\\}$ implying that if
$z\notin\\{m,a,b,2m-t,g\\}$, then $z$ is non-contributing, a contradiction.
Lemmas 4.3 and 4.4 imply that

  * •

$z=a$ and $\alpha+\zeta=\gamma$,

  * •

$z=g$ and $\gamma+\zeta=\beta$, or

  * •

$z=2m-t$.

If $z=a$, then $z=t$ and Lemma 2.15 implies $g=a+z-m=a+t-m=b$, contradicting
that $D_{g}\in S$. If $z=g$, then Lemma 2.15 implies $b=z+g-m=2g-m$.
Additionally, since $t=a$, it follows that $b=t+a-m=2a-m$. So, $g=a$, again
contradicting that $D_{g}\in S$. Thus, $z=2m-t$. If $\alpha+\zeta=\gamma$,
then Lemma 2.15 implies $g=a+z-m=a+(2m-t)-m=a+(2m-a)-m=m$, contradicting that
$D_{g}\in S$. So, $\gamma+\zeta=\beta$. This means
$c(\zeta)\in\\{c(\beta),c(\gamma)\\}$. And since $c(D_{2m-t})\subseteq
c(D_{m})\cup\\{c(\alpha),c(\beta)\\}$, it follows that $c(\zeta)=c(\beta)$.
Recall that $c(\beta)\in c(D_{2m-t})$ only if $c(\delta)=c(\beta)$. Since
$\delta\in D_{a}$, $c(\alpha),c(\beta)\in c(D_{a})$, contradicting Lemma 2.7.
Thus, it has finally been shown that $b=2m-t$. ∎

Theorem 4.9 says that there are no jumps between distinctly colored elements
whose colors do not appear in the main diagonal. First it is shown that
$|D_{m}|=4$ and one of $D_{t},D_{a},D_{b}$ is non-contributing, so by Lemma
2.10, all other off-diagonals are contributing. Next, some $\gamma\in D_{g}$
and $\zeta\in D_{z}$ are found such that $\alpha+\zeta=\gamma$ or
$\gamma+\zeta=\beta$. Since $D_{z}$ must be contributing, $z\in\\{g,a,b,t\\}$,
and Lemma 4.3 and 4.4 imply that $\alpha+\zeta=\gamma$ and $z=a$ or
$\gamma+\zeta=\beta$ and $z=g$. In either case, a contradiction is found.

######  Theorem 4.9.

Let $c$ be an exact, rainbow free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $3\leq m\leq n$, and suppose there is a jump from $\alpha\in D_{a}$
to $\beta\in D_{b}$ such that $\alpha+\delta=\beta$ for some
$\delta=(d_{1},d_{2})\in D_{t}$. Then $c(\alpha)\in c(D_{m})$ or $c(\beta)\in
c(D_{m})$ or $c(\alpha)=c(\beta)$.

###### Proof.

For the sake of contradiction, assume $c(\alpha),c(\beta)\notin c(D_{m})$ and
$c(\alpha)\neq c(\beta)$. Corollary 2.9 and Lemma 3.2 imply $4\leq|c(D_{m})|$.
Lemma 2.5 and Corollary 4.7 further restrict to the situation to $8\leq m\leq
10$, $n\leq 13$, $5\leq d_{1}+d_{2}\leq 7$, and $|c(D_{m})|=4$. Additionally,
Lemma 4.8 implies $2m-t=b$.

Since $a=b$, $a=t$, or $b=t$ implies $m\in\\{t,a,b\\}$, it follows that $a$,
$b$, and $t$ are pairwise distinct. Specifically, $t<m<b<a$ or $a<b<m<t$. The
solution $\alpha+\delta=\beta$ means $c(\delta)\in\\{c(\alpha),c(\beta)\\}$.
Now, Lemma 2.10 implies that two of $D_{t},D_{a},D_{b}$ contribute $c(\alpha)$
and $c(\beta)$ and the third is non-contributing. Thus, every diagonal $D_{k}$
with $k\notin\\{m,t,a,b\\}$ must contribute a color distinct from $c(\alpha)$
and $c(\beta)$.

Define $S$ as in (1). Note that

$|S|=\begin{cases}d_{1}+d_{2}-3&\text{if
$m\notin\\{D_{x}\,|\,m+a_{2}-b_{1}<x<m+b_{2}-a_{1}\\}$},\\\
d_{1}+d_{2}-4&\text{if
$m\in\\{D_{x}\,|\,m+a_{2}-b_{1}<x<m+b_{2}-a_{1}\\}$}\end{cases}$

and observe $1\leq|S|$. It is claimed that $1\leq|S\setminus\\{D_{t}\\}|$.
Indeed, if $D_{t}\in S$, then $|S|\geq 3$ since if $t<m<b$, it follows that

$m+a_{2}-b_{1}<t\leq b-2=m-b_{1}+b_{2}-2$

so that

$2<b_{2}-a_{2}=d_{2}<d_{1}$

which implies $d_{1}+d_{2}\geq 7$, thus $d_{1}+d_{2}=7$. A similar case holds
for $b<m<t$.

Let $D_{g}\in S\setminus\\{D_{t}\\}$, and note that $D_{g}$ must contribute a
color. Say $D_{g}$ contributes $c(\gamma)$ for some $\gamma\in D_{g}$. By
Lemmas 2.13 and 2.14, there exists a $\zeta\in D_{z}$ such that
$\alpha+\zeta=\gamma$ or $\gamma+\zeta=\beta$. Note that
$c(\zeta)\in\\{c(\gamma),c(\alpha),c(\beta)\\}$, so $z\in\\{g,a,b,t\\}$. By
Lemmas 4.3 and 4.4, this can only happen if $\alpha+\zeta=\gamma$ and $z=a$,
or $\gamma+\zeta=\beta$ and $z=g$.

Case 1.

Suppose $\alpha+\zeta=\gamma$ and $z=a$.
Lemma 2.15 implies

$g=2a-m=m-2a_{1}+2a_{2}.$

Since $D_{g}\in S$, it follows that $g<m+b_{2}-a_{1}$ implying

$a_{2}-a_{1}<b_{2}-a_{2}=d_{2}$

and similarly the lower bound implies $a_{1}-a_{2}<d_{1}$. In the case when
$t<m<a$, then $d_{2}<d_{1}$ and $a_{1}<a_{2}$. Since $d_{1}+d_{2}=7$,
$0<a_{2}-a_{1}<3$. Similarly, if $a<m<t$, then $0<a_{1}-a_{2}<3$. Since $b$ is
between $m$ and $a$, this would require $a=m+2$ or $a=m-2$. Then $b=m+1$ and
$g=m+4$ or $b=m-1$ and $g=m-4$, respectively.

First, suppose $a=m+2$. Since $D_{m+4}\in S$, it follows that
$D_{g^{\prime}}:=D_{m+3}\in S$ and so there exists a $\gamma^{\prime}\in
D_{g^{\prime}}$ such that $D_{m+3}$ contributes $c(\gamma^{\prime})$. By
Lemmas 2.13 and 2.14, there exists a jump $\zeta^{\prime}\in D_{z^{\prime}}$
from $\alpha$ to $\gamma^{\prime}$ or from $\gamma^{\prime}$ to $\beta$, with
$c(\zeta^{\prime})\in\\{c(\gamma^{\prime}),c(\alpha),c(\beta)\\}$. By Lemmas
4.3 and 4.4, this can only happen if $\zeta^{\prime}$ is a jump from $\alpha$
to $\gamma^{\prime}$ and $z^{\prime}=a$, or $\zeta^{\prime}$ is a jump from
$\gamma^{\prime}$ to $\beta$ and $z^{\prime}=g^{\prime}$. If
$z^{\prime}=a=m+2$, then $g^{\prime}=m+4$ since $\zeta^{\prime}$ is a jump
from $\alpha$ to $\gamma^{\prime}\in D_{g^{\prime}}$. Likewise, if
$z^{\prime}=g^{\prime}=m+3$ then $b=m+6$. In either case, a contradiction
arises.

Similar contradictions can be found when $a=m-2$.

Case 2.

Suppose $\gamma+\zeta=\beta$ and $z=g$.

Then $b=2g-m$. Additionally, since $t=2m-b$ and $b=a+t-m$, it follows that
$a=2b-m$. Combining these equations yields $a=4g-3m$ implying

$g=\frac{3m+a}{4}=m+\frac{a_{2}-a_{1}}{4}.$ (9)

In parallel to Case 1, since $D_{g}\in S$, it follows that $g<m+b_{2}-a_{1}$
implying $a_{2}-a_{1}<4b_{2}-4a_{1}$ and

$3(a_{1}-a_{2})<4(b_{2}-a_{2})=4d_{2}.$

Similarly, the lower bound on $S$ implies $3(a_{2}-a_{1})<4d_{1}$. In the case
when $a<m<t$, then $d_{1}<d_{2}$ and $a_{2}<a_{1}$. Since $d_{1}+d_{2}=7$, it
follows that $0<a_{1}-a_{2}<\frac{4}{3}d_{2}\leq 8$. Likewise, if $t<m<a$,
then $0<a_{2}-a_{1}<8$. Note that Equation (9) implies $a_{1}-a_{2}=4(m-g)$,
i.e. $4$ divides $a_{1}-a_{2}$. So, $a=m+4$ or $a=m-4$. In the former case,
$D_{m+3}\in S$ with $m+3\notin\\{g,t\\}$, and in the latter, $D_{m-3}\in S$
with $m-3\notin\\{g,t\\}$. Lemmas 2.13, 2.14,4.3 and 4.4 yield similar
contradictions to those in Case 1.

Therefore, $c(\alpha)\in c(D_{m})$ or $c(\beta)\in c(D_{m})$ or
$c(\alpha)=c(\beta)$. In other words, there are no jumps between distinctly
colored elements. ∎

##  5 Rainbow number of $[m]\times[n]$ for $x_{1}+x_{2}=x_{3}$

This final section uses definitions that were introduced in Section 2 which
can be visualized with the help of Figure 2. In particular, definitions of
$W$, $Y$, $P_{h}$ and $P_{v}$ are used.

Three lemmas and the final results are presented. The first lemma gives a
lower bound on the number of consecutive contributing diagonals and, provided
a horizontal or vertical pair intersects $W$, the second gives upper bounds on
vertical and horizontal pairs, respectively. These results are leveraged
against the third lemma, a relatively unconditional and straightforward upper
bound on the total number of horizontal and vertical pairs, to yield Theorem
5.4. This theorem gives $\operatorname{rb}([m]\times[n],eq)=m+n+1$ for all
$8\leq m\leq n$. Along with several earlier statements to cover the cases of
$2\leq m\leq 7$, Theorem 5.4 subsequently determines the final result and the
result claimed to be true in the exposition of this paper, Theorem 5.5.

######  Lemma 5.1.

If $c$ is an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for $eq$
with $3\leq m\leq n$, then there are at least $m+n-2\log_{2}(m/s_{2})-2$ pairs
of consecutive, contributing off-diagonals.

###### Proof.

Define $\ell=|c(D_{m})|$ and notice that Corollary 2.11 gives at least
$m+n-\log_{2}(m/s_{2})-1$ contributing off-diagonals and Lemma 2.10 gives at
most $\ell-3$ non-contributing off-diagonals. If all of the contributing off-
diagonals were consecutive, then there would be $m+n-\log_{2}(m/s_{2})-2$
pairs of consecutive, contributing off-diagonals. However, every non-
contributing diagonal, including every non-contributing off-diagonal and
$D_{m}$, when inserted between two consecutive, contributing off-diagaonals,
can reduce the count of pairs of consecutive, contributing off-diagonals by at
most one. Finally, since Lemma 2.5 implies $\ell\leq\log_{2}(m/s_{2})+2$,
there are at least

$(m+n-\log_{2}(m/s_{2})-2)-(\ell-2)\geq m+n-2\log_{2}(m/s_{2})-2$

pairs of consecutive, contributing off-diagonals. ∎

######  Lemma 5.2.

Let $c$ be an exact, rainbow-free $(m+n+1)$-coloring of $[m]\times[n]$ for
$eq$ with $4\leq m\leq n$. If there is a horizontal pair $P_{h}$ intersecting
$W$, then there are at most $2s_{2}-2$ vertical pairs in $[m]\times[n]$.
Likewise, if there is a vertical pair $P_{v}$ intersecting $W$, then there are
at most $2s_{2}-2$ horizontal pairs in $[m]\times[n]$.

###### Proof.

Note that if $|c(D_{m})|=3$ then $c$ is not rainbow-free by Theorem 3.4 so
assume $|c(D_{m})|\geq 4$. Then, Lemma 2.5 gives $s_{2}\leq m/4$. Further,
Lemma 5.1 implies at least $m+n-2\log_{2}(m/s_{2})-2$ pairs of consecutive,
contributing off-diagonals. At most $2(2s_{2}-2)$ of these pairs are entirely
contained in $Y$ so at least $m+n-2\log_{2}(m/s_{2})-2-2(2s_{2}-2)$ pairs of
consecutive, contributing off-diagonals that intersect $W$. Using $4\leq m\leq
n$, $m/s_{2}\leq m/2$, $4s_{2}\leq m$ and $\log_{2}(x)$ is increasing gives

$m+n-2\log_{2}(m/s_{2})-2-2(2s_{2}-2)\geq m-2\log_{2}(m)+4\geq 4.$

That is, there are at least $4$ pairs of consecutive, contributing off-
diagonals that intersect $W$. Further, Theorem 4.9 indicates that these pairs
are either horizontal or vertical. Thus, if any of these pairs that intersect
$W$ is a horizontal pair, there cannot also be a vertical pair that intersects
$W$ without creating a contributing disjoint corner which, by Lemma 2.16,
implies $c$ is not rainbow-free. Thus, all vertical pairs must be contained
completely within $Y$. Only half of the pairs in $Y$ can be vertical so, in
this case, there are are most $2s_{2}-2$ vertical pairs in $[m]\times[n]$. A
similar result is obtained when it is assumed that a vertical pair intersects
$W$.∎

######  Lemma 5.3.

Let $c$ be an exact, rainbow-free (m+n+1)-coloring of $[m]\times[n]$ for $eq$
with $3\leq m\leq n$. Then, there are at most $n-1$ possible horizontal pairs,
and there are at most $m-1$ vertical pairs.

###### Proof.

Lemma 2.7 and Theorem 4.9 imply that two distinct horizontal pairs cannot both
intersect the $i$th and $(i+1)$th columns, and two distinct vertical pairs
cannot both intersect the $j$th and $(j+1)$th rows. Since there are $n-1$
pairs of consecutive columns and $m-1$ pairs of consecutive rows, the desired
result is obtained. ∎

######  Theorem 5.4.

If $c$ is an exact $(m+n+1)$-coloring of $[m]\times[n]$ with $8\leq m\leq n$,
then $[m]\times[n]$ contains a rainbow solution to $eq$.

###### Proof.

Assume, for the sake of contradiction, that $c$ is rainbow-free. By Theorem
3.4, $|c(D_{m})|\geq 4$. Now, Lemma 2.5 implies $4\leq\log_{2}(m/s_{2})+2$ so
that $m\geq 4s_{2}$.

Case 1.

There exists a horizontal pair intersecting $W$.

By Lemma 5.1, there exist at least $m+n-2\log_{2}(m/s_{2})-2$ pairs of
consecutive contributing off-diagonals. By Theorem 4.9, there are at least
$m+n-2\log_{2}(m/s_{2})-2$ consecutive contributing pairs of elements which
each must be a vertical or horizontal pair. Since Lemma 5.2 implies there at
most $2s_{2}-2$ vertical pairs, there must be at least
$m+n-2\log_{2}(m/s_{2})-2s_{2}$ horizontal pairs in $[m]\times[n]$.

Using $m/s_{2}\leq m/2$, $s_{2}\leq m/4$, $8\leq m$ and that $\log_{2}(x)$ is
increasing, it follows that

$m+n-2\log_{2}(m/s_{2})-2s_{2}\geq n+m/2-2\log_{2}(m)+2\geq n>n-1,$

contradicting Lemma 5.3.

Case 2.

There exists a vertical pair intersecting $W$.

Using an argument similar to the first case shows that there must be at least
$m+n-2\log_{2}(m/s_{2})-2s_{2}$ vertical pairs $[m]\times[n]$. Again,

$m+n-2\log_{2}(m/s_{2})-2s_{2}>n-1\geq m-1,$

contradicting Lemma 5.3.

Since both cases give a contradiction, $c$ is not rainbow-free. ∎

Combining Lemma 2.6, Corollary 2.8, Theorem 3.4, and Theorem 5.4 gives Theorem
5.5.

######  Theorem 5.5.

If $2\leq m\leq n$ , then $\operatorname{rb}([m]\times[n],eq)=m+n+1$.

###### Proof.

First, Corollary 2.8 gives the desired result when $m=2$. Now, Lemma 2.6 gives
that $m+n+1\leq\operatorname{rb}([m]\times[n],eq)$ for $3\leq m\leq n$. For
$3\leq m\leq 7$, at most three colors are in the main diagonal so Theorem 3.4
gives $\operatorname{rb}([m]\times[n],eq)=m+n+1$. Finally, for $8\leq m\leq
n$, Theorem 5.4 gives $\operatorname{rb}([m]\times[n],eq)=m+n+1$.∎

## Acknowledgements

Thank you to the University of Wisconsin-La Crosse (UWL) Deans Distinguished
Fellows program that supported the third and sixth authors. Thanks also to UWL
Undergraduate Research and Creativity grants that supported the first, third
and sixth authors. Finally, thanks to UWL Department of Mathematics and
Statistics Bange/Wine Undergraduate Research Endowment that supported the
third author.

## References

  * [1] K. Ansaldi, H. El Turkey, J. Hamm, A. Nu’Man, N. Warnberg and M. Young. Rainbow Numbers of $\mathbb{Z}_{n}$ for $a_{1}x_{1}+a_{2}x_{2}+a_{3}x_{3}=b$. _INTEGERS_ , 20, A51 (2020). http://math.colgate.edu/~integers/vol20.html
  * [2] M. Axenovich and D. Fon-Der-Flaass, On rainbow arithmetic progressions, _Electron. J. Combin._ 11 (2004), no. 1, Research Paper 1, 7pp. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r1
  * [3] Z. Berikkyzy, A. Schulte, E. Sprangel, S. Walker, N. Warnberg and M. Young. Anti-van der Waerden Numbers on Graphs. _Graphs and Combinatorics_ , 38(124) (2022). https://doi.org/10.1007/s00373-022-02516-9
  * [4] Z. Berikkyzy, A. Schulte, and M. Young, Anti-van der Waerden numbers of 3-term arithmetic progressions, _Electron. J. Combin._ 24 (2017), no. 2, Paper 2.39, 9 pp. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p39
  * [5] E. Bevilacqua, A. King, J. Kritschgau, M. Tait, S. Tebon and M. Young, Rainbow numbers for $x_{1}+x_{2}=kx_{3}$ in $\mathbb{Z}_{n}$, _INTEGERS_ , 20, A50 (2020). http://math.colgate.edu/~integers/vol20.html
  * [6] S. Butler, C. Erickson, L. Hogben, K. Hogenson, L. Kramer, R.L. Kramer, J. Lin, R.R. Martin, D. Stolee, N. Warnberg and M. Young, Rainbow Arithmetic Progressions, _J. Comb._ 7(4) (2016), 595–626.https://www.intlpress.com/site/pub/pages/journals/items/joc/content/vols/0007/0004/a003/index.php
  * [7] K. Fallon, C. Giles, H. Rehm, S. Wagner and N. Warnberg, Rainbow numbers of $[n]$ for $\sum_{i=1}^{k-1}x_{i}=x_{k}$, _Austral. J. Combin._ 77(1) (2020), 1–8.https://ajc.maths.uq.edu.au/pdf/77/ajc_v77_p001.pdf
  * [8] M. Huicochea and A. Montejano, The Structure of Rainbow-Free Colorings For Linear Equations on Three Variables in $\mathbb{Z}_{p}$, _Integers_ 15A (2015), A8. http://math.colgate.edu/~integers/vol15a.html
  * [9] V. Jungić, J. Licht (Fox), M. Mahdian, J. Nes̆etril, and R. Radoic̆ić, Rainbow arithmetic progressions and anti-Ramsey results, _Combinatorics, Probability and Computing_ 12 (2003), no 5-6, 599–620. https://doi.org/10.1017/S096354830300587X
  * [10] B. Llano and A. Montejano, Rainbow-free Colorings of $x+y=cz$ in $\mathbb{Z}_{p}$, _Discrete Math._ 312, (2012), 2566–2573. https://doi.org/10.1016/j.disc.2011.09.005
  * [11] J. Miller and N. Warnberg, Anti-van der Waerden Number of Graph Products of Cycles, https://arxiv.org/abs/2205.11621.
  * [12] H. Rehm, A. Schulte and N. Warnberg, Anti-van der Waerden numbers on Graph Products, _Austral. J. Combin._ 73(3) (2019), 486–500. https://ajc.maths.uq.edu.au/pdf/73/ajc_v73_p486.pdf
  * [13] K. Uherka, An introduction to Ramsey theory and anti-Ramsey theory on the integers, Master’s Creative Component (2013), Iowa State University.
  * [14] M. Young. Rainbow Arithmetic Progressions in Finite Abelian Groups, _J. Comb._ 9(4) (2018), 619–629. https://www.intlpress.com/site/pub/pages/journals/items/joc/content/vols/0009/0004/a003/index.php