\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}