\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{graphicx}
\usepackage{amsmath, amsthm}

% Math commands
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Zpd}{\mathbb{Z}_p^d}
\newcommand{\Zp}{\mathbb{Z}_p}
\newcommand{\Zn}{\mathbb{Z}_n}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\divides}{|}
\newcommand{\vect}[1]{{\bf #1}}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}




\title{Toward a graph version of Rado's theorem}

\author{Andy Parrish\\
\small Department of Mathematics\\[-0.8ex]
\small University of California, San Diego\\[-0.8ex]
\small La Jolla, California, U.S.A.\\
\small\tt atparrish@math.ucsd.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jan 23, 2013}{XX}\\
\small Mathematics Subject Classifications: 05D10}

\begin{document}
\maketitle


\begin{abstract}
\noindent
An equation is called {\it graph-regular} if it always has
monochromatic solutions under edge-colorings of $K_{\N}$.
We present two Rado-like conditions which are respectively
necessary and sufficient for an equation to be graph-regular.
\end{abstract}

\bigskip\noindent \textbf{Keywords:} coloring; graph theory; Ramsey theory; Rado's theorem

\section{Introduction}

Ramsey's theorem \cite{GRS}\cite{ramsey} states that, given numbers $r$ and $k$,
there is an $R=R(r,k)$ so that any $r$-coloring of the edges of the
complete graph on $R$ vertices contains a monochromatic complete graph
on $k$ vertices.

Elsewhere in Ramsey theory, the related (but seemingly-unconnected)
result of Rado \cite{GKP}\cite{GRS}\cite{rado} characterizes the set
of linear equations $A \vect{x} = \vect{0}$ such that, whenever $\N$
is finitely colored, there is a solution whose entries fall into
the same color class. Such an equation is called {\it partition-regular}.

These two results were connected in a result by Deuber, Gunderson, Hindman,
and Strauss \cite{gunder1}, and followed up by Gunderson, Leader, Pr\"omel,
and R\"odl \cite{gunder2}\cite{gunder3}.  Their results describe the equations
$A \vect{x} = \vect{0}$ such that, for any $m$, a large two-colored graph must
either contain a complete blue subgraph whose vertices solve the equation,
or a red $K_m$ with no implied structure. If one can assure that there is
no red $K_m$, then the desired structured set falls out nicely.

The first example of an equation with an unconditional monochromatic solution
was given in \cite{parrish}. That paper introduced the notion of a
{\it graph-regular} equation.

\begin{definition}
For a fixed matrix $A$ and vector $\vect{b}$, we say $A \vect{x} = \vect{b}$
is graph-regular if there is a function
$N_A(r)$ so that, for all $r$, for all $N > N_A(r)$, every $r$-coloring of
the complete graph on $[N]$ has a solution $\vect{x} = (x(1), \ldots, x(k))$
so that (1) the edges $\{x(i), x(j)\}$ are all the same color,
and (2) the values $\{x(i)\}$ are distinct.
\end{definition}

We require a solution by distinct values due to degeneracy issues which do not
appear in the case of coloring points. Further, for non-triviality, we require
the equation to contain at least three variables.

As the main contribution of this paper, we give two extensions of Rado's
``columns condition'' to the graph setting ---
the {\it weak} and {\it strong} graph columns conditions.
We will show that the weak version is necessary for an equation to be
graph-regular, and the strong version is sufficient.

The two sets of graph columns conditions are introduced in
Section~\ref{se:GCC}. In Section~\ref{se:necessary}, we show that the
weak graph columns condition is necessary for graph-regularity,
and along the way we show that $A \vect{x} = \vect{b}$ may only be
graph-regular if $\vect{b} = \vect{0}$.
Section~\ref{se:sufficient} shows that the strong graph columns condition
is sufficient for graph-regularity.
Finally, in Section~\ref{se:hypergraphs}, we explore the natural extension
of this problem to hypergraph-regular equations, and find that the condition
is too strong --- no such equation exists.




%\input{columnscondition}
\section{The Graph Columns Condition}\label{se:GCC}

\subsection{Definitions}

Rado's theorem \cite{GRS}\cite{rado} characterizes the partition-regular
equations with use of the columns condition. Here we state a new formulation
which is equivalent to the original.

\begin{definition}\label{de:CC}
A matrix $A$ satisfies the columns condition if there is a
sequence of vectors $\vect{z}_1, \ldots, \vect{z}_T$ in the nullspace of $A$
and decreasing sequence of sets $R_1 \supseteq \ldots \supseteq R_T$
so that
\begin{enumerate}
\item If $i \in R_t$, then $z_s(i)=0$ for all $s \le t$.
\item If $i \notin R_t$, then there is an $s \le t$ with $z_s(i) = 1$
\item $R_T = \varnothing$.
\end{enumerate}
\end{definition}
Here is another perspective, closer to the usual.
For a fixed $i$, the sequence of values $\{z_t(i)\}_{t=1}^T$
is restricted to being 0 until some $z_t(i)$ is 1, after which it is free
to take on any value. Hence the sets $R_t$ denote which variables are
still {\it restricted} at time $t$.

The remarkable fact, proven originally in \cite{rado}, and in \cite{GRS},
is that the columns condition determines whether an equation is regular.

\begin{theorem}\label{th:rado}
The equation $A \vect{x} = \vect{0}$ has a monochromatic solution under
any finite coloring of $\N$ whenever $A$ satisfies the columns condition.
If $A$ does not satisfy the columns condition then there is some
$p_0 = p_0(A)$ so that, for every prime $p > p_0$, a monochromatic solution
is avoided by the coloring $\psi_p$
(which will be introduced in Section~\ref{se:sumtozero}).
\end{theorem}

There are several ways to extend the columns condition to apply to
edge-colorings. We state two.

\begin{definition}\label{de:GCC}
We say a matrix $A$ with $n$ columns satisfies the
{\it weak graph columns condition} (WGCC) if there is a sequence of vectors
$\vect{z}_0, \ldots, \vect{z}_T$ in the nullspace of $A$,
and a decreasing sequence of graphs $R_0 \supseteq \ldots \supseteq R_T$ with
common vertex set $[n]$ so that
\begin{enumerate}
\item If $\{i, j\} \in R_t$, then $z_s(i)=z_s(j)$ for all $s < t$.
\item If $\{i, j\} \notin R_t$, then there is an $s \le t$ with
  $|z_s(j) - z_s(i)| = 1$.
\item $R_T = \varnothing$.
\item $\vect{z}_0 = \vect{1}$.
\end{enumerate}

Further, we say $A$ satisfies the {\it strong graph columns condition} (SGCC)
if we may replace (1) and (2) by ($1^*$) and ($2^*$):
\begin{enumerate}
\item[$1^*.$] If $\{i, j\} \in R_t$, $z_s(i)=z_s(j) \in \{0, 1\}$
  for all $s < t$
\item[$2^*.$] If $\{i, j\} \notin R_t$, then there is an $s \le t$ with
  $z_s(i) = 0$ and $z_s(j) = 1$ (or vice versa).
\end{enumerate}
\end{definition}


In words, the $\vect{z}_t$'s are restricted so that, for each $i, j$ pair,
as $t$ increases, the values $z_t(i), z_t(j)$ are initially equal, remain
equal until they differ by exactly 1, and are unrestricted after that.
An edge between $i$ and $j$ in graph $R_t$ means that pair remains restricted
through time $t$. If $\{i, j\} \in R_t$, then we say
the pair is {\it restricted} at time $t$, otherwise it is {\it unrestricted}.

The strong graph columns conditions requires conditions on the values
$z_t(i)$ in addition to the differences across edges.

\begin{example}\label{ex:6vars}
Let
\[
A = \left( \begin{array}{rrrrrr}
1 & -1 & 0 & -1 & 4 & -3\\
0 &  0 & 1 & -1 & 1 & -1\\
\end{array} \right).
\]
Here is one sequence of vectors showing $A$ satisfies
the graph columns condition (weak and strong):
\[
\vect{z}_0 = \left(
\begin{array}{c}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\
\end{array}
\right) \qquad
\vect{z}_1 = \left(
\begin{array}{c}
1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\
\end{array}
\right) \qquad
\vect{z}_2 = \left(
\begin{array}{c}
1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\
\end{array}
\right) \qquad
\vect{z}_3 = \left(
\begin{array}{c}
3 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \\
\end{array}
\right)
\]
The corresponding restriction graphs may be described simply:
\begin{itemize}
\item $R_0$: All edges are restricted --- $R_0 = K_6$.
\item $R_1$: All edges among \{1, 2\} and \{3, 4, 5, 6\} remain restricted.
\item $R_2$: Edges \{3, 4\} and \{5, 6\} remain restricted.
\item $R_3$ is empty --- no edges are restricted.
\end{itemize}
Note that, at each step, $R_t$ is a union of
disjoint cliques. This always happens.
\end{example}


\begin{example}\label{ex:8vars}
Fix any nonzero $r \in Q$. Let
\[
A = \left( \begin{array}{rrrrrrrc}
1 & -1 & 0 &  0 & 0 &  0 & -1 &   1 \\
0 &  0 & 1 & -1 & 0 &  0 & -1 &   1 \\
0 &  0 & 0 &  0 & 1 & -1 & -1 &   1 \\
0 & -1 & 0 & -1 & 0 & -1 & -r & r+1 \\
\end{array} \right).
\]
Here is one sequence of vectors showing $A$ satisfies
the weak graph columns condition:
\[
\vect{z}_0 = \left(
\begin{array}{c}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\
\end{array}
\right) \qquad
\vect{z}_1 = \left(
\begin{array}{c}
1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\
\end{array}
\right) \qquad
\vect{z}_2 = \left(
\begin{array}{c}
1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \\
\end{array}
\right) \qquad
\vect{z}_3 = \left(
\begin{array}{c}
1 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \\ r+1 \\ r \\
\end{array}
\right)
\]

Notice that $\vect{z}_3$ relaxes the restriction on the 7th and 8th columns
by using values $r$ and $r+1$, rather than 0 and 1 as required by the strong
graph columns condition. Indeed, $A$ satisfies WGCC, but fails to satisfy SGCC.
We believe 8 variables is minimal to separate these conditions.
\end{example}

We now state our main result:

\begin{theorem}\label{th:goal}
Fix a matrix $A$.
If $A \vect{x} = \vect{0}$ is graph-regular,
then $A$ satisfies the weak graph columns condition.
If $A$ satisfies the strong graph columns condition,
then $A \vect{x} = \vect{0}$ is graph-regular.
\end{theorem}

We will prove WGCC is necessary in Section~\ref{se:necessary}.
The proof is based on both the techniques and result of Rado,
and is not particularly deep.
In Section~\ref{se:sufficient}, we will show SGCC is sufficient.
The proof uses the machinery from \cite{parrish} to expand the family
of known graph-regular equations which were missed on the first pass.

Of course the most interesting question here is to close the gap
between the strong and weak conditions --- to classify the remaining
equations. Is the matrix from Example~\ref{ex:8vars} graph-regular?



%\input{necessary}
\section{Necessary conditions for graph-regularity}\label{se:necessary}

In this section, we define the appropriate colorings which allow us
to essentially repeat the proof of Rado's theorem for our setting.
After these colorings show some initial structure of graph-regular
equations, we will apply Rado's theorem to show that WGCC is necessary.

\subsection{Coefficients must add to 0}\label{se:sumtozero}
We define a family of colorings, $f_n$, of $\binom{\N}{2}$ by
\[
f_n(an+x,bn+y) = \left\{
\begin{array}{ll}
\hbox{blue}  & \hbox{if } x = y     \\
\min \{x,y\} & \hbox{if } x \neq y, \\
\end{array}
\right.
\]
where $x,y \in \{0, 1, \ldots, n-1\}$, and where we storm past the
usual boundary between {\it actual} colors and mathematician's colors.
We claim that all monochromatic triangles under $f_n$ are blue.

Consider a triangle $\{x, y, z\}$ with no blue edge,
where $x = an+i,y=bn+j,z=cn+k$, and $i,j,k \in \{0,1,\ldots,n-1\}$.
Then the numbers $i,j,k$ must be distinct. Reordering so that $i < j < k$,
we see that $f_n(x,y) = f_n(x,z) = i$, while $f_n(y,z)=j \neq i$.
Thus a triangle without a blue edge cannot be monochromatic. Turning this
around, any monochromatic triangle must be blue.

Going back to the definition of $f_n$, this means that any monochromatic
triangle --- and hence any monochromatic clique --- must represent only
one congruence class mod $n$.

\begin{lemma}\label{le:divides}
If $\sum a_i x_i = b$ is graph-regular with $b, a_i \in \Z$,
then $b$ is a multiple of $\sum a_i$.
\end{lemma}

\begin{proof}
Write $\sum a_i = M$. If $M \neq 0$, then consider the coloring $f_M$.
Let $\{x_i\}$ be monochromatic under $f_M$, so that $x_i = b_i M + c$.

Then we have
\[
\begin{array}{rcl}
\sum a_i x_i & = & \sum a_i (b_i M + c) \\
             & = & \left( \sum a_i b_i M \right) + \sum a_i c \\
             & = & \left( \sum a_i b_i \right) M + c M. \\
\end{array}
\]
We see that $\sum a_i x_i$ is a multiple of $M$. If $\sum a_i x_i = b$,
then we see that $b$ is a multiple of $M$ as well.

On the other hand, if $M = 0$, then we may repeat the above argument
using any $f_n$. Since the $c M$ term goes away, we learn that $b$
is a multiple of $n$ for every $n$ we choose, forcing $b = 0$ as well.
\end{proof}

Fix $n$, and define the coloring $g_n$ of $\binom{\N}{2}$ by
\[
g_n(n^j a, n^k b) = \left\{
\begin{array}{ll}
\hbox{red}   & \hbox{if } j \neq k \\
f_n(a,b)     & \hbox{if } j = k,   \\
\end{array}
\right.
\]
where $a$ and $b$ are not divisible by $n$.

\begin{note}\label{no:gpColors}
Using the same argument as for $f_n$, we see that any triangle which is
monochromatic under $g_p$ must be red or blue for $p$ prime.
Writing $x_i = b_i n^{r_i}$, this means either all $r_i$ values are distinct
(yielding a red clique), or all $r_i$ values are equal and all $b_i$ values
are congruent modulo $n$ (yielding a blue clique).
\end{note}

\begin{lemma}\label{le:sumtozero}
If $\sum a_i x_i = b$ is graph-regular with $b, a_i \in \Z$,
then $\sum a_i = b = 0$.
\end{lemma}

\begin{proof}
Suppose $\sum a_i x_i = b$ is graph-regular, with $M = \sum a_i \neq 0$.
By Lemma~\ref{le:divides}, we may write $b = k M$.
We assume each $a_i$ is non-zero, as removing superfluous variables
will preserve graph-regularity.

We apply a new coloring, which should be thought of as a hybrid
between the colorings $f_n$ and $g_n$. There is a prime $p$ which does not
divide $M$ nor any of the $a_i$ values, since none of these values is 0.
For any $x$, we may uniquely write $x = cp + d + k$, where
$d \in \{0, 1, \ldots, p-1\}$ and $k = \frac{b}{M}$ was defined above.

Using this form, we define
\[
\chi(cp + d + k, c'p + d' + k) = \left\{
\begin{array}{ll}
\min \{d, d'\} & \hbox{if } d \neq d', \\
g_p(c, c')     & \hbox{if } d = d'     \\
\end{array}
\right.
\]

Note that we treat the colors from the two pieces of this function
as distinct --- all pairs in a monochromatic clique must have either
all used the first piece, or all used the second. In fact, we have
already seen from our analysis of $f_n$ that no monochromatic clique
can arise from the first piece of the definition of $\chi$, so any
solution must come from $g_p$.

Let $\{x_i\}$ be a monochromatic solution. Since all edges must have
been colored by the second piece of $\chi$, we can write
$x_i = \beta_i p + d + k$, where $d \in \{0, 1, \ldots, p-1\}$ is
common for each $x_i$.\footnote{
For small values of $x_i$, the resulting $\beta_i$ may be zero or negative.
A little care is required to handle $\beta_i = 0$, but we will ignore it here.}
This gives us
\[
\begin{array}{rcl}
\sum a_i x_i                             & = & b  \\
\sum a_i \left(\beta_i p + d + k \right) & = & kM \\
\sum a_i \beta_i p + dM + kM             & = & kM \\
\left( \sum a_i \beta_i \right) p + dM   & = & 0. \\
\end{array}
\]
Since $p$ does not divide $M$, and $d$ is less than $p$, we must have $d = 0$. Dividing by $p$,
we are left with
\[
\sum a_i \beta_i = 0.
\]

Write $\beta_i = (b_i p + c_i) p^{r_i}$, with $c_i \in \{1, 2, \ldots, p-1\}$.
From Note~\ref{no:gpColors}, we have either a red clique with
each $r_i$ distinct, or we have a blue clique with $r_i=r$ and $c_i=c$
common across all $i$.

\noindent
{\bf Case 1.}\;\;The clique is blue, so $\beta_i = (b_i p + c) p^r$.

We see that
\[
\begin{array}{rcl}
\sum a_i (b_i p + c) p^r & =      & 0          \\
\sum a_i (b_i p + c)     & =      & 0          \\
\sum a_i c               & \equiv & 0 \pmod{p} \\
c M                      & \equiv & 0 \pmod{p}.\\
\end{array}
\]
Since $p$ divides neither $c$ nor $M$, this is impossible.

\noindent
{\bf Case 2.}\;\;The clique is red, so $\beta_i = (b_i p + c_i) p^{r_i}$,
with each $r_i$ distinct.

Let $r_j$ be the unique smallest exponent. We find
\[
\begin{array}{rcl}
\sum a_i (b_i p + c_i) p^{r_i}                                      & =      & 0          \\
\sum a_i (b_i p + c_i) p^{r_i - r_j}                                & =      & 0          \\
a_j (b_j p + c_j) + \sum_{i \neq j} a_i (b_i p + c_i) p^{r_i - r_j} & =      & 0          \\
a_j c_j.                                                            & \equiv & 0 \pmod{p} \\
\end{array}
\]
Again, since $p$ divides neither $c$ nor $a_j$, this is impossible.

\vspace{1pc}
Together, we have seen that $M \neq 0$ is impossible, so $\sum a_i = M = 0$.
Since $b = k M$, we also get $b = 0$ for free.
\end{proof}

Note that Lemma~\ref{le:sumtozero} extends to systems of linear equations ---
if $A \vect{x} = \vect{b}$ is graph-regular,
then $\vect{b} = \vect{0}$ and the columns of $A$ sum to $\vect{0}$. This is
easily seen since each equation from the system $A \vect{x} = \vect{b}$
must also be graph-regular.

Consider such an equation, $\vect{a}_1 x_1 + \ldots + \vect{a}_k x_k = 0$,
where the coefficients sum to 0. We may rewrite this as, for instance,
\[
\vect{a}_1 (x_1 - x_k) + \ldots + \vect{a}_{k-1} (x_{k-1} - x_k) = 0,
\]
now an equation relating differences.
This suggests that we should consider colorings based on these differences
--- colorings of the form $\chi(x < y) = f(y-x)$. We may now take guidance
from Rado's theorem to get a better handle on things.

For a prime $p$, and $x = p^r (bp + s)$, let $\psi_p(x) = s \in [p-1]$
be the ``super mod $p$'' coloring, from Rado's theorem.
Rado's theorem suggests to us that, when looking at colorings
based only on differences between endpoints, we need only consider the
colorings $\psi_p$. We will show that Rado's theorem does apply here,
but we begin with a simple consequence to give a feel for how it works.

\begin{theorem}\label{th:partition}
Let $\sum_{i=1}^k a_i x_i = 0$ be graph-regular with $a_i \in \Z$.
Then there is a nonempty set $I \subsetneq [k]$ so that
\[
\sum_{i \in I} a_i = \sum_{j \notin I} a_j = 0.
\]
\end{theorem}
To prove this, we introduce the graph version of $\psi_p$.

Define $\varphi_p : \binom{\N}{2} \rightarrow [p-1]$ by
\[
\varphi_p(x < y) = \psi_p(y - x).
\]

\begin{proof}
Fix a prime $p$ and color $\binom{\N}{2}$ by $\varphi_p$.
Suppose $x_1, \ldots, x_k$ are distinct values satisfying
$a_1 x_1 + \ldots + a_k x_k = 0$, with the edges among them all color $c$.
Let $x_j$ be the smallest of these values. As noted earlier, we see that
\[
\sum_{i \neq j} a_i (x_i - x_j) = 0.
\]
By choice of $x_j$, each of the terms $x_i - x_j$ is positive.
Thus we may write $x_i - x_j = p^{r_i} (b_i p + c)$, since
$\varphi_p(x_j < x_i) = \psi_p(x_i-x_j) = c$. Let $r$ be the
smallest exponent among these $k-1$ terms, and let
$I = \{i \in [k]\setminus\{j\} \mid r_i = r\}$. Note that
$\varnothing \subsetneq I \subsetneq [k]$.
We see that
\[
\begin{array}{rcl}
0 & = & \displaystyle \sum_{i \neq j} a_i p^{r_i} (b_i p + c)\\
  & = & \displaystyle \sum_{i \neq j} a_i p^{r_i - r} (b_i p + c)\\
  & = & \displaystyle \sum_{i \in I} a_i (b_i p + c) +
        p \left( \sum_{i \notin I \cup \{j\}}
                 a_i p^{r_i - r - 1} (b_i p + c) \right)\\
  & \equiv & \displaystyle c \left( \sum_{i \in I} a_i \right) \pmod{p}\\
\end{array}
\]
Since $c$ is in $[p-1]$, we see that $p$ divides $\sum_{i \in I} a_i$.
If we take $p > \sum_{i=1}^k |a_i|$, then the only way
this can happen is if $\sum_{i \in I} a_i = 0$. Since we already know that
$\sum_{i=1}^k a_i = 0$, we learn that $\sum_{j \notin I} a_j = 0$ as well.
\end{proof}

\begin{corollary}
No nondegenerate homogeneous linear equation of three variables
is graph-regular.
\end{corollary}

This was already proven in \cite{parrish} using Brooks' theorem, but we
give a simpler proof.

\begin{proof}
Let $k = 3$, and let $I \subsetneq \{1,2,3\}$ be nonempty. Then either
$I$ or its complement has a single element. The corresponding coefficient
must be 0, meaning the equation depends on at most two variables and is
trivial.
\end{proof}

\begin{corollary}
Up to rescaling, the only graph-regular homogeneous linear equation
of four variables is $w-x+y-z=0$.
\end{corollary}

That this equation is regular was shown in \cite{parrish}. We show that
it stands alone.

\begin{proof}
Let $aw+bx+cy+dz=0$ be graph-regular, with $a,b,c,d \in \Z_{\neq 0}$.
By Theorem~\ref{th:partition}, we know that two complementary subsets
of the coefficients must add to zero. Up to permutation, this leaves
us with $aw-ax+cy-cz=0$, or rather $a(w-x)=c(z-y)$. We may assume both
$a$ and $c$ are positive by switching $w$ and $x$, or $y$ and $z$.
We claim $a = c$.

Suppose not. After canceling common factors, we may assume we may
assume $c$ is divisible by some prime $p$ which does not divide $a$.
Pick $r$ so that $p^r$ divides $c$, but $p^{r+1}$ does not.
Consider the 2-coloring given by
\[
\chi(x,y) \equiv \left\lfloor \frac{f(x,y)}{r} \right\rfloor \pmod{2},
\]
where $f(x,y)$ gives the highest exponent of $p$ which divides $x-y$.

Now suppose $a(w-x) = c(z-y)$, with $w,x,y,z$ distinct.
Let $f(w,x) = k$. This means that $a(w-x)$ represents a power of
$p^k$ on the left hand side. Dividing by $c$, we learn that
$(z-y)$ represents a power of $p^{k-r}$,
so $f(y,z) = k-r$. Looking at the corresponding $\chi$ values of
$\{w,x\}$ and $\{y,z\}$, we see that they are different,
so the edges among $\{w,x,y,z\}$ are not monochromatic.
\end{proof}




\subsection{Considering $\varphi_p$}

\begin{lemma}\label{le:phip}
Let $A$ be a matrix whose columns sum to $\vect{0}$.
If the equation $A \vect{x} = \vect{0}$ has a monochromatic solution under
the edge-coloring $\varphi_p$ for every prime $p$, then $A$ satisfies the
weak graph columns condition.
\end{lemma}

\begin{proof}
Let $A \vect{x} = \vect{0}$ have a monochromatic solution under $\varphi_p$ for
every prime $p$. Denote the columns of $A$ by $\{ \vect{a}_i \}_{i=1}^n$.

From $A$, we will make a larger matrix $C$ with columns indexed by
$\binom{[n]}{2} = \{ (i,j) \mid 1 \le i < j \le n \}$.
The columns of $C$ come from gluing the columns of $A$ (or the zero vector)
to new vectors which bind relationships between the columns of $A$.

\[
\vect{c}_{1j} = \left( \begin{array}{c}
\vect{a}_j \\
\hbox{---} \\
\vect{b}_{1j}
\end{array} \right),
\hbox{ and }
\vect{c}_{ij} = \left( \begin{array}{c}
\vect{0} \\
\hbox{---} \\
\vect{b}_{ij}
\end{array} \right)
\hbox{ if } i > 1,
\]
where
\[
b_{ij}(k,\ell) = \left\{ \begin{array}{ll}
 1 & \hbox{if } (k,\ell) = (1,j) \\
-1 & \hbox{if } (k,\ell) = (1,i) \hbox{ or } (i,j)\\
 0 & \hbox{otherwise.}
\end{array} \right.
\]

Note that the matrix $C$ does not explicitly contain the column
$\vect{a}_1$. However, since $\sum \vect{a}_i = \vect{0}$, that information
is not lost.

Suppose $C \vect{y} = \vect{0}$, with $y(1,j) = x(j) - x(1)$.
The vectors $\{ b_{ij} \}$ are designed so that $y(i,j) = x(j) - x(i)$.

Turned around, when $A \vect{x} = \vect{0}$, and $\vect{y}$ is defined above,
we get $C \vect{y} = \vect{0}$. Likewise, if $C \vect{y} = \vect{0}$ then,
for any value $x(1)$, the values $x(i)$ are uniquely defined from
$\vect{y}$, and they satisfy $A \vect{x} = \vect{0}$.

We would like to say that, when $A \vect{x} = \vect{0}$ is a monochromatic
solution under the edge-coloring $\varphi_p$, the corresponding solution to
$C \vect{y} = \vect{0}$ is monochromatic under the vertex-coloring $\psi_p$.
However, this is not quite true.
The definition says $\varphi_p(x,y) = \psi_p(y-x)$ only when $x < y$.
For a monochromatic solution under $\psi_p$, we would need
$x(1) < x(2) < \ldots < x(n)$.
Instead, for each permutation $\sigma \in S_n$, we must define the matrix
$C(\sigma)$ which will ``work'' when
$x(\sigma_1) < x(\sigma_2) < \ldots < x(\sigma_n)$.
We omit the definition of $C(\sigma)$, but it is essentially the same as $C$,
defined in such a way that $y(i,j)$ is always a positive number
when $\vect{x}$ is ordered by $\sigma$.

If $\vect{x}$ is a solution to $A \vect{x} = \vect{0}$, with
$x(\sigma_1) < x(\sigma_2) < \ldots x(\sigma_n)$,
then there is a corresponding solution to $C(\sigma) \vect{y} = \vect{0}$
by positive numbers, where $y(i,j) = x(\sigma(j)) - x(\sigma(i))$.
When $\vect{x}$ is monochromatic under $\varphi_p$,
$\vect{y}$ is monochromatic under $\psi_p$.

We claim that some $C(\sigma)$ satisfies the columns condition.
Indeed, by Rado's theorem, any $C(\sigma)$ failing to satisfy the columns
condition has a monochromatic solution to $C(\sigma) \vect{y} = \vect{0}$
under $\psi_p$ for only finitely many primes $p$. Since each $p$ yields
some $\sigma$ for which there is a solution, we learn
that some $C(\sigma)$ gives a solution for infinitely many values of $p$.
That $C(\sigma)$ must satisfy the columns condition.

Fix such a $\sigma$. For simplicity, we reorder the columns of $A$ so that
$\sigma$ is the identity, and $C(\sigma)$ is the matrix $C$ described
originally.

The columns condition gives us vectors $\vect{w}_1, \ldots, \vect{w}_T$
indexed by $\binom{[n]}{2}$,
and sets $R_1 \supseteq \ldots \supseteq R_T = \varnothing$ with vertex set
$\binom{[n]}{2}$ satisfying conditions (1)-(3) of Definition~\ref{de:CC}.

Define a sequence of vectors $\vect{z}_1, \ldots, \vect{z}_T$ on $[n]$
by $z_t(1) = 0$, and $z_t(i) = w_t(1,i)$ for $i > 1$.
Additionally define $\vect{z}_0 = \vect{1}$ and $R_0 = \binom{[n]}{2}$.
We just need $\{ \vect{z}_t \}, \{ R_t \}$ to satisfy
requirements (1)-(4) of the graph columns condition.

It will be helpful to know that, for $k < \ell$,
\begin{equation}\label{eq:difference}
z_t(\ell) - z_t(k) = w_t(k,\ell)
\end{equation}
To see this, consider the $\{k,\ell\}$ row of the vectors $\vect{b}_{ij}$ within $C$.
Since $C \vect{w} = \vect{0}$, inspecting this row tells us that
\[
w_t(1,\ell) - w_t(1,k) = w_t(k,\ell).
\]
By definition of $\vect{z}_t$, we see that
\[
z_t(\ell) - z_t(k) = w_t(k,\ell)
\]
as desired.

Using this equation, properties (1)-(3) are immediate. Property (4) comes from
the assumption that the columns of $A$ sum to $\vect{0}$.
\end{proof}

\begin{corollary}
If a matrix $A$ is graph-regular, then it satisfies the weak graph columns
condition.
\end{corollary}

\begin{proof}
From Lemma~\ref{le:sumtozero}, we know that the columns of $A$ sum to
$\vect{0}$. Since $A$ is graph-regular, it must have a monochromatic solution
under $\varphi_p$ for every prime $p$. By Lemma~\ref{le:phip},
$A$ satisfies the weak graph columns condition.
\end{proof}

We end this section by considering the sufficiency of the WGCC.

\begin{corollary}
If a matrix $A$ satisfies the weak graph columns condition but is not
graph-regular, then the offending coloring is {\it not} of the form
$\chi(x < y) = f(y-x)$.
\end{corollary}

To see this in action, consider the coloring $\varphi_p$ and the matrix
$A$ from Example~\ref{ex:8vars}. Suppose that $1 < r < p^k-1$.
Consider the vector $\vect{x}$ in the nullspace of $A$ given by
\[
\vect{x} = (p^{k+2} + 1) \vect{z}_1 + (p^{k+1} + p) \vect{z}_2 + p^2 \vect{z}_3
\]
where $\{ \vect{z}_i \}$ come from the analysis of this example earlier.
It is easy to check that $x(1) > x(2) > \ldots > x(8)$, and that $\varphi_p$
colors all edges by ``1''.
Indeed, Lemma~\ref{le:phip} actually shows that all colorings based on the
difference of the endpoints will yield a monochromatic solution.
Therefore, if the equation $A \vect{x} = \vect{0}$ is not graph-regular,
it must be from some other type of coloring.




%\input{sufficient}
\section{Sufficient conditions for graph-regularity}\label{se:sufficient}

We now prove the strong graph columns condition. We only have one tool
at our disposal to actually find a monochromatic solution to a general
edge coloring --- the machinery from \cite{parrish}. In order to get more
mileage out of it, we define a large, hierarchical parameterized grid,
which we call a $Grid_n$.
The details of the definition are chosen to capture all of the monochromatic
structure guaranteed in that paper.

\begin{definition}
Fix $\vect{x}, \vect{y}, \vect{b}, \vect{d} \in \N^n$. We say the grid of
depth $n$ with parameters $\vect{x}, \vect{y}, \vect{b}, \vect{d}$
--- abbreviated $Grid_n(\vect{x}, \vect{y}, \vect{b}, \vect{d})$ ---
is the collection of points $A = \bigcup_{k=1}^n A_k$ where $A_k$ is the
set of points of the form
\[
\left( \sum_{\ell=1}^{k-1} h(\ell)d(\ell) + x(k)d(k) + i d(k+1),
       \sum_{\ell=1}^{k-1} h(\ell)d(\ell) + y(k)d(k) + j d(k+1) \right)
\]
such that $h(\ell) \in \{x(\ell), y(\ell)\}$ and $i,j \in [-c(k), c(k)]$
for some $c(k) \ge b(k)$. As it is not earlier defined, we use $d(n+1)=0$.

For such a grid to behave nicely, we always require the parameters to
satisfy:
\begin{enumerate}
\item $d(k)$ divides $d(k+1)$,
\item $x(k)b(k), y(k)b(k) \le c(k-1)$.
\end{enumerate}
\end{definition}

As a technical note, the use of $c(k) > b(k)$ comes from requirement (2).
%For our purposes, we will only make explicit use of coefficients up to $b(k)$.

We say that a $Grid_n(\vect{x}, \vect{y}, \vect{b}, \vect{d})$
is ``proper'' if (a) all $x$-coordinates of each of its points is less than
all $y$-coordinates, and (b) each coordinate has a unique
representation of the form
\[
\sum_{\ell=1}^{k} h(\ell)d(\ell) + i d(k+1)
\]
over all values of $k \in [n]$, $h(\ell) \in \{x(\ell), y(\ell)\}$,
and $i, j \in [-c(k), c(k)]$. We may thus unambiguously say that a point
``resides at the $k^{th}$ level'' of the grid if its coordinates agree on
$h(\ell)$ for all $\ell < k$, but disagree on $h(k)$.

\vspace{1pc}
\noindent
For convenience of notation, we will treat a proper $Grid_n$ as a graph,
since it uniquely stores pairs $\{x, y\}$.

The definition of a $Grid_n$ is admittedly overwhelming; It is best to think
hierarchically. A $Grid_1$ (or the $A_1$ portion of a $Grid_n$) is simply
a square grid of lattice points $(x + id, y + jd)$ for $i, j \in [-c, c]$.
The value $c$ is chosen to be at least the prescribed minimum bound $b$.
A $Grid_1$ is exactly what is guaranteed monochromatic by the Gallai-Witt
theorem \cite{GKP}\cite{GRS}. The definition here appears slightly more
general, but nothing is lost by assuming $d(1) = 1$.
When we view points as the edges of a graph, this grid will correspond
to a complete bipartite graph between two sets of arithmetic progressions
--- the vertices $\{x + id\}$ on one side, and $\{y + jd\}$ on the other.

A $Grid_2$ extends a $Grid_1$, and is given by $A_1 \cup A_2$. Beyond
the $Grid_1$, it includes two additional grids of the same type:
one with points of the form $(x+x'd+id', x+y'd+jd')$,
and the other with points $(y+x'd+id', y+y'd+jd')$
where $d'$ is a multiple of the original $d$. As before, each of these
grids correspond to complete bipartite graphs between two arithmetic
progressions. Better, because of points (1) and (2) above, in each case the
two progressions are actually sub-progressions of the ones from the $Grid_1$.
That is, we now have four progressions --- anchored at
$x+x'd,\;x+y'd,\;y+x'd,$ and\;$y+y'd$ respectively --- so that the complete
4-partite graph among them is contained in the $Grid_2$.

Continuing this logic, a $Grid_n$ includes a complete $2^n$-partite
graph on arithmetically-related points, as well as some other edges.

The proof of Theorem 3.1 in \cite{parrish} may be easily modified to give
the following lemma.

\begin{lemma}\label{le:monogrid}
Fix $\vect{b} \in \N^n$. There is a number $Q = Q(r, \vect{b})$ so that
every $r$-coloring of $[Q]^2$ admits vectors
$\vect{x}, \vect{y}, \vect{d} \in \N^n$ such that
$Grid_n(\vect{x}, \vect{y}, \vect{b}, \vect{d})$ is proper and monochromatic.

Moreover, the dependencies are such that the value of $b(k)$ may be a function
of upper bounds for $x(k+1), y(k+1), c(k+1),$ and $\frac{d(k+1)}{d(k)}$.
\end{lemma}

This lemma tells that we can always find a ``large'' monochromatic
$Grid_n$.

\subsection{A $Grid_n$ is enough}

Since we know every finite-coloring of $[Q] \times [Q]$ contains a
large monochromatic $Grid_n$ (for $Q$ sufficiently large),
we only need to show the following.

\begin{lemma}\label{le:solningrid}
Let $A$ satisfy the strong graph columns condition. Then there is some $n$,
$\vect{b}$ so that the following holds. For every every proper
$G = Grid_n(\vect{x}, \vect{y}, \vect{b}, \vect{d})$, there is a solution to
$A \vect{w} = \vect{0}$ so that, for all $i,j$, the edge
$\{w(i), w(j)\}$ is in $G$.

In particular, if $A$ satisfies the strong graph columns condition
in $T$ steps, then we may take $n = T$.
\end{lemma}

\begin{proof}
Let $A$ satisfy the columns condition, by vectors
$\vect{z}_0=\vect{1}, \vect{z}_1, \ldots, \vect{z}_T$ and graphs
$R_0 \supseteq \ldots \supseteq R_T = \varnothing$.

Fix $\vect{x}, \vect{y}, \vect{d} \in \N^T$. Define a sequence of vectors by
\[
\vect{v}_t = x(t)d(t) \vect{z}_0 + (y(t) - x(t))d(t) \vect{z}_t
           = x(t)d(t) \vect{1}   + (y(t) - x(t))d(t) \vect{z}_t,
\]
each in the nullspace of $A$.

Define $\vect{w} = \sum_{t=1}^{T} \vect{v}_t$. As a sum of
vectors in the nullspace of $A$, we have $A \vect{w} = \vect{0}$.
We claim that this is the desired solution.
It remains to show show that (1) every edge $\{w(i), w(j)\}$ is in $G$, and
(2) the values $w(i)$ are distinct.

Fix two indices $i$ and $j$. By the strong columns condition, we know that
the values $z_t(i)$ and $z_t(j)$ are initially equal --- with common value
0 or 1 --- when $\{i, j\} \in R_t$. There is a first time $t^*$ such that
(without loss of generality) $z_{t^*}(i)=0$ and $z_{t^*}(j)=1$.

Moving to $\vect{w}$, we see that
$z_t(i)=0$ contributes $x(t)$ to $w(i)$, and
$z_t(i)=1$ contributes $y(t)$ to $w(i)$.
Since $v_t(i)$ and $v_t(j)$ agree for $t < t^*$, we may call the common
contribution at the $t$ step $h(t) = x(t)$ or $y(t)$. At time $t^*$,
$v(i) = x(t^*)$ while $v(j) = y(t^*)$. This suggests the edge
$\{ w(i), w(j) \}$ should reside at the $(t^*)^{th}$ level of $G$.
For $t > t^*$, we have
\[
\renewcommand{\arraystretch}{1.5}
\begin{array}{rcll}
|v_t(i)| &  =  & | x(t)d(t) + (y(t) - x(t))d(t)z_t(i) | \\
         &  =  & | x(t) + (y(t) - x(t))z_t(i) | \times d(t) \\
         & \le & | y(t) + y(t) z_t(i) | \times d(t)
                   & \hbox{since } 0 \le x(t) \le y(t) \\
         & \le & \left( \|z_t\|_{\infty} + 1 \right) y(t) d(t) \\
\end{array}
\renewcommand{\arraystretch}{1}
\]
Thus we see the total contribution to $w(i)$ from the tail of the sum comes to
\[
\renewcommand{\arraystretch}{1.5}
\begin{array}{rcll}
\displaystyle \left| \sum_{s > t^*} v_t(i)\right |
    & \le & \displaystyle \sum_{s > t^*} \left( \|z_s\|_{\infty} + 1 \right) y(s) d(s) \\
    & \le & \left( \|z_{t^*+1}\|_{\infty} + 1 \right) y(t^*+1) d(t^*+1) +
            \ldots + \\
    &     & + \left( \|z_{T-1}\|_{\infty} + 1 \right) y(T-1) d(T-1) +
            \left( \|z_{T}\|_{\infty} + 1 \right) y(T) d(T)\\
\end{array}
\renewcommand{\arraystretch}{1}
\]
We now begin to see an appropriate choice of $\vect{b}$. Set
\[
b(T) \ge \|z_{T}\|_{\infty} + 1.
\]
The last term of our bound above becomes
$b(T) y(T) d(T)$, which by assumption is less than $c(T-1) d(T)$.

Next take
\[
b(T-1) \ge \left( \|z_{T-1}\|_{\infty} + 1 \right) y(T-1) +
           c(T-1) \left( \frac{d(T)}{d(T-1)} \right).
\]

Now the last two terms of the sum are bounded by $c(T-2) d(T-1)$.

We may continue this process so that, for $t > t^*$, we have
\[
b(t) \ge \left( \|z_{t}\|_{\infty} + 1 \right) y(t) +
         c(t) \left( \frac{d(t+1)}{d(t)} \right).
\]

Working backwards to step $t^* + 1$, we get
\[
\displaystyle \left| \sum_{t > t^*} v_t(i)\right | \le c(t^*) d(t^* + 1).
\]

We have written
\[
\renewcommand{\arraystretch}{1.5}
\begin{array}{rcll}
w(i) & = & h(1)d(1) + \ldots + h(t^* - 1) d(t^* - 1) + x(t^*) d(t^*) +
           p d(t^* + 1) \\
w(j) & = & h(1)d(1) + \ldots + h(t^* - 1) d(t^* - 1) + y(t^*) d(t^*) +
           q d(t^* + 1) \\
\end{array}
\renewcommand{\arraystretch}{1}
\]
with $p, q \in [-c(t^*), c(t^*)]$. Thus we see $\{w(i), w(j)\}$ is indeed
a point in $G$, in the $(t^*)^{th}$ level.

To wrap up this argument, we need only take $b(t)$ to be the maximum of the
lower bounds seen, over all choices of $i$ and $j$.

Finally, showing the points are distinct is simple. Since
$z_{t^*}(i) = 0$ and $z_{t^*}(j) = 1$, we see that $w(i)$ involves $x(t^*)$,
while $w(j)$ involves $y(t^*)$. Since the grid is proper, the values $w(i)$
and $w(j)$ must be distinct.
\end{proof}


\begin{corollary}
Let $A$ satisfy the strong graph columns condition.
Then $A \vect{x} = \vect{0}$ is graph-regular.
\end{corollary}

\begin{proof}
Let $\vect{c}$ be the vector given in Lemma~\ref{le:solningrid},
and let $r \in \N$ be a number of colors.
We claim that, if $Q \ge Q(r, \vect{c})$ from Lemma~\ref{le:monogrid},
then any $r$-coloring of $\binom{[Q]}{2}$ will contain a solution to
$A \vect{x} = \vect{0}$ so that the values $\{x(i)\}$ are distinct,
and the edges $\{ x(i), x(j) \}$ are monochromatic.

Indeed, by Lemma~\ref{le:monogrid}, viewing $\chi$ as an $r$-coloring of
$[Q] \times [Q]$ (minus the diagonal), we find a monochromatic $Grid_n$
of distinct points, with size at least $\vect{c}$.
By Lemma~\ref{le:solningrid}, this $Grid_n$ contains a solution to
$A \vect{x} = \vect{0}$ as desired.
\end{proof}





%\input{hypergraphs}
\section{Hypergraph-regular equations}\label{se:hypergraphs}


There is a natural extension of graph-regularity to the hypergraph Ramsey
theorem.

Unfortunately, this extension is not fruitful.
Say a homogeneous linear equation is ``$r$-graph-regular'' if, for every
coloring of the $r$-sets of $\N$, it has a monochromatic solution by
distinct numbers. As with graphs, when considering an $r$-uniform hypergraph,
we require the equations to have at least $r+1$ variables, or else every
solution will be trivially monochromatic.

\begin{theorem}
For $r \ge 3$, no homogeneous linear equation of at least $r+1$ variables
is $r$-graph-regular for $r$-uniform hypergraphs.
\end{theorem}

\begin{proof}
We show the result for $r = 3$, and suggest the appropriate modifications
for higher $r$.

Assume each $a_i$ is nonzero, since discarding trivial variables only makes
it easier to be graph-regular.

For any $n$, define an $(n+1)$-coloring $f_n^{(3)}$ of $\binom{\N}{r}$ by
\[
f_n^{(3)}(an+x,bn+y,cn+z) = \left\{
\begin{array}{ll}
\hbox{blue}  & \hbox{if } x=y=z \\
\min \{x,y,z\} & \hbox{if one of } {x,y,z} \hbox{ is smallest} \\
\max \{x,y,z\} & \hbox{otherwise,} \\
\end{array}
\right.
\]
where $x,y,z \in \{0, 1, \ldots, n-1\}$. Similar to before, any set of four
elements which is monochromatic under this coloring must be blue.

Now define $g_n^{(3)}$ on $\binom{\N}{r}$ by
\[
g_n^{(3)}(n^i a, n^j b, n^k c) = \left\{
\begin{array}{ll}
f_{n-1}^{(3)}(a,b,c) & \hbox{if } i=j=k \\
\hbox{red}     & \hbox{if one of } {i,j,k} \hbox{ is smallest} \\
\hbox{green}   & \hbox{otherwise,} \\
\end{array}
\right.
\]
where $a,b,c$ are not divisible by $n$. Again, similar to before, any
monochromatic clique under this coloring on at least four points must
be red or blue. The proofs of Lemmas~\ref{le:divides} and \ref{le:sumtozero}
now apply essentially unchanged to show that the coefficients of a
hypergraph-regular equation must sum to zero.

Therefore, we only consider $\sum_{i=1}^k a_i x_i = 0$ where
$\sum a_i = 0$.

Define a new coloring, $h_n(x,y,z) = g_n(y-x,z-x)$, where
$x < y < z$, and $g_n$ is the graph-coloring used in
Section~\ref{se:sumtozero}.

Suppose $x_1, \ldots, x_k$ are distinct values satisfying
$\sum a_i x_i = 0$, with the hyperedges among them monochromatic ---
either red or blue.
Let $x_j$ be the smallest of these values. Since
$a_j = -\sum_{i \neq j} a_i$, we see that
\[
\sum_{i \neq j} a_i (x_i - x_j) = 0.
\]
By choice of $x_j$, we see that $\{x_i - x_j\}_{i \neq j}$ is monochromatic
under $g_n$. As before, a red clique means some $a_i$ is 0.
If the clique is blue, then $\sum_{i \neq j} a_i = 0$, meaning $a_j = 0$.
Since none of the coefficients are 0, we have reached a contradiction.
Thus no homogeneous linear equation in at least 4 variables is
hypergraph-regular under colorings of 3-sets.

\bigskip
\noindent
For a general $r$-uniform hypergraph with $r > 3$, one can easily modify
the definition of $g_n^{(3)}$ to find a suitable $g_n^{(r)}$,
which will force coefficients to add to zero.
Likewise, one may define a coloring similar to $h_n$ which is built
upon $g_n^{(r-1)}$, which will force one of the coefficients to
be zero. These two colorings together will avoid solutions to
any equation in at least $r+1$ variables.
\end{proof}


Evidently, the ability to color 3-sets (or higher) of integers is too strong
to permit monochromatic solutions to homogeneous linear equations.
Is there a better definition for an equation to be $r$-graph-regular which
allows some equations to meet it, or is this the end of the story?



\begin{thebibliography}{99}

\bibitem{gunder1}
  W. Deuber, D. S. Gunderson, N. Hindman, D. Strauss,
  {\it Independent finite sums for $K_m$-free graphs},
  J. Combin. Theory Ser. A 78 (1997), no. 2, 171-198.

\bibitem{GKP}
  W. Gasarch, C. Kruskal, A. Parrish, {\it Van der Waerden's theorem
  and its variants}, to appear.

\bibitem{GRS}
  R.L. Graham, B.L. Rothschild, J. Spencer, {\it Ramsey Theory},
  John Wiley \& Sons Inc., New York, second edition 1990.

\bibitem{gunder2}
  D. S. Gunderson, I. Leader, H. J. Pr\"omel, and V. R\"odl,
  {\it Independent arithmetic progressions in clique-free graphs
  on the natural numbers}, J. Combin. Th. Ser. A 93 (2001), 1-17.

\bibitem{gunder3}
  D. S. Gunderson, I. Leader, H. J. Pr\"omel, and V. R\"odl,
  {\it Independent Deuber sets in graphs on the natural numbers},
  J. Combin. Th. Ser. A 103 (2003), 305-322.

\bibitem{parrish}
  A. Parrish, {\it An additive version of Ramsey's theorem}. J. Comb. 2 (2011), no. 4, 593-613.

\bibitem{rado}
  R. Rado, {\it Studien zur Kombinatorik}, Math. Zeit. 36 (1933), 242-280.

\bibitem{ramsey}
  F. P. Ramsey, {\it On a problem in formal logic},
  Proc. London Math. Soc. (2), 30 (1930), 264-286.

\end{thebibliography}

%\bibliographystyle{abbrv}
%\bibliography{bibfile}

\end{document}
