%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-11/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}
%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}
\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}
%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
\gdef\@thm@name{#3}%
\@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
\edef\@currentlabel{\@thm@name}%
\label{#1}\endgroup
}
\makeatother
% end lift
\newtheoremstyle{namedthrm}
{}{}{}{}{}{}{ } % This last space needs to be there
{\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack
%% Document start
\date{}
\begin{document}
%% Content start
\newtheorem{thrm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{conj}{Conjecture}
\title{Monochromatic structures in colorings of the positive integers and the finite subsets of the positive integers}
\author{Tom Brown\footnote{Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada V5A 1S6. \texttt{tbrown@sfu.ca}.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Monochromatic structures in colorings of the positive integers
and the finite subsets of the positive integers}, 15th MCCCC (Las Vegas, NV,
2001). J. Combin. Math. Combin. Comput. \textbf{46} (2003), 141--153.}\bigskip\end{center}
\begin{abstract}We discuss van der Waerden's theorem on arithmetic progressions
and an extension using Ramsey's theorem, and the canonical versions. We
then turn to a result (Theorem \ref{t11-6} below) similar in character
to van der Waerden's theorem, applications of Theorem \ref{t11-6}, and
possible canonical versions of Theorem \ref{t11-6}. We mention several
open questions involving arithmetic progressions and other types of
progressions.
\end{abstract}
\section{van der Waerden's theorem on arithmetic progressions}
One of the great results in combinatorics is the following theorem.
\begin{thrm}\label{t11-1} (van der Waerden's theorem on arithmetic
progressions) If $N$ is finitely colored (= finitely partitioned)
then some color class (= cell of the partition) contains arbitrarily
large arithmetic progressions $P = \{ a,a+d,a+2d,\ldots,a+(n-1)d\}$.
\end{thrm}
Van der Waerden's original proof is in \cite{vanderwaerden1927}. The most famous proof
(essentially van der Waerden's own proof) is in \cite{khinchin1998}. See also
\cite{vanderwaerden1971}. The shortest proof is in \cite{graham+rothschild+spencer1990}. The clearest proof is
probably in \cite{mills1983}. A topological proof can be found in \cite{furstenberg+weiss1978}.
For other proofs, see \cite{anderson1976,bergelson+furstenberg+hindman+katznelson1989,
compton1999,deuber1982,promel+rodl1986,promel+rothschild1987,shelah1988,taylor1982,walters2000}.
The ''canonical'' version of van der Waerden's theorem is the following,
due to Erd\H{o}s and Graham \cite{erdos+graham1980}.
\begin{thrm}\label{t11-2} Given $f:N\to\omega = \{0,1,2,\ldots\}$,
there exist arbitrarily large arithmetic progressions $P$ such that
$f|_P$ is either constant or 1-1.\end{thrm}
An equivalent form of van der Waerden's theorem is the following.
\begin{thrm}\label{t11-3} For all $k\geq1$ there exists a (smallest)
$\omega(k)$ such that every 2-coloring of $[1,\omega(k)]$ produces a
monochromatic $k$-term arithmetic progression.\end{thrm}
Using the definition of $\omega(k)$ from the preceding theorem, the
only known values of $\omega(k)$ are $\omega(1) = 1$, $\omega(2) = 3$,
$\omega(3) = 9$, $\omega(4) = 35$, $\omega(5) = 178$. For values involving
more than two colors, see \cite{bate+skillicorn1981,beeler+oneil1971,
chvatal1970,huang+yang2000,stevens+shantaram1978}.
Berlekamp \cite{berlekamp1968} showed in 1961 that $k2^k<\omega(k+1)$ if $k$ is prime.
Erd\H{o}s asked in 1961 whether or not $\lim_{k\to\infty}\frac{\omega(k)}{2^k}
=\infty$, and offered US \$25 for an answer. This question is still open,
and the prize is still available.
Szabo \cite{szabo1990} showed in 1990 that $\frac{2^k}{k^\epsilon} < \omega(k)$,
$k>k(\epsilon)$.
Gowers showed in 1998 \cite{gowers1998,gowers2001} that $\omega(k) < 2^{2^{2^{2^{2^{k+9}}}}}$.
Graham asked in 1998 whether $\omega(k) < 2^{k^2}$, and offers US \$1000 for
an answer.
Using Ramsey's theorem, the following ``extended'' van der Waerden's theorem
can be proved.
\begin{thrm}\label{t11-4} (Extended van der Waerden's theorem) If $P_f(\mathbb{N})$
(the collection of all finite subsets of $\mathbb{N}$) is finitely colored,
then for every $n\geq1$ there exist an infinite set $Y\subseteq\mathbb{N}$ ($Y$
depends on $n$) and an arithmetic progression $\{a,a+d,a+2d,\ldots,a+(n-1)d\}$
such that the set $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$
is monochromatic. (Here $[Y]^k$ denotes the set of all $k$-element subsets of
$Y$.)\end{thrm}
\begin{proof}Let $g:P_f(\mathbb{N})\to[1,r]$ be an $r$-coloring of $P_f(\mathbb{N})$.
Let $n$ be given. By van der Waerden's theorem, choose $m$ large enough that
every $r$-coloring of $[1,m]$ produces a monochromatic $n$-term arithmetic
progression. Using Ramsey's theorem, choose infinite sets $X_1,X_2,\ldots,X_m$
in turn so that $Y = X_m\subseteq X_{m-1}\subseteq\cdots\subseteq X_2\subseteq X_1
\subseteq\mathbb{N}$ and $g$ is constant on each of $[X_k]^k$, $1\leq k\leq m$.
($[X_k]^k$ denotes the set of all $k$-element subsets of $X_k$.) Let us suppose
that (for each $k$) $g(A) = a_k$ for all $A$ in $[X_k]^k$.
Let $h:[1,m]\to[1,r]$ be defined by setting $h(k)=a_k$, $1\leq k\leq m$. By the
choice of $m$, there exist positive integers $a,d$ such that $h(a) = h(a+d)
= h(a+2d) = \cdots = h(a + (n-1)d)$. This means that $g$ is constant on the
set $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$, and the
proof is complete.\end{proof}
The following was pointed out by Shi Lingsheng, a student of Hans Juergen
Proemel: Suppose $X$ is any finite collection of subsets of $\mathbb{N}$
such that every finite coloring of $\mathbb{N}$ produces arbitrarily large
monochromatic elements of $X$. Then for every finite coloring of $P_f(\mathbb{N})$
and every $n$, there exists an infinite set $Y$ ($Y$ depends on $n$) and an
element $A$ of $X$ of size $n$, such that $\bigcup [Y]^x$ is monochromatic,
where the union is over all $x$ in $A$. The proof is exactly as above. Thus
for example, using Folkman's theorem, for every finite coloring of $P_f(\mathbb{N})$
and every $n$, there exists an infinite set $Y$ ($Y$ depends on $n$) and
distinct positive integers $a_1,a_2,\ldots,a_n$ such that $\bigcup [Y]^x$ is
monochromatic, where the union is over all $x$ such that $x$ is a sum of
distinct $a_1,a_2,\ldots,a_n$.
It would be of interest to find a canonical version of Theorem \ref{t11-4}.
(One would likely need to use the canonical version of van der Waerden's theorem
above, as well as the canonical version of Ramsey's theorem.)
This has not yet been done. However, one can get a canonical theorem (Theorem
\ref{t11-5} below) for a structure somewhat smaller (but still very large!)
than $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$.
From the set $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}\cup\cdots\cup[Y]^{a+(n-1)d}$
one can easily construct a forest $F$ with the following properties:
\begin{enumerate}
\item Each vertex of $F$ is a finite subset of $Y$.
\item $F$ has $n$ levels, and each vertex at a level $i$ has $a+id$ elements,
$0\leq i\leq n-1$.
\item Vertex $y$ at level $i+1$ covers vertex $x$ at level $i$ iff $x\subset
y$.
\item If $y,z$ cover $x$ then $y\cap z = x$.
\item Each element of $Y$ appears in at most one tree of the forest $F$.
\item Each vertex not at level $n-1$ has infinitely many immediate successors.
\item $F$ is the union of infinitely many non-empty trees.
\end{enumerate}
Let us call such a structure an ``arithmetic $\omega$-forest of height $n$.''
Diana Piguetova, a student of Jarik Ne\u{s}et\u{r}il, has proved the following
result.
\begin{thrm}\label{t11-5} If $g:P_f(\mathbb{N})\to\omega$ is an arbitrary
coloring, then for every $n\geq 1$ there exists an arithmetic $\omega$-forest
$F$ of height $n$ on which the coloring $g$ has one of the following patterns:
\begin{enumerate}
\item $g|_F$ is constant.
\item Each tree is monochromatic, and different trees have different colors.
\item Each level in the whole forest is monochromatic, all of different colors.
\item Each level in each tree is monochromatic, all of different colors.
\item $g|_F$ is 1-1.
\end{enumerate}\end{thrm}
\section{A theorem involving ``almost arithmetic progressions''}
Van der Waerden's theorem guarantees large arithmetic progressions, but says
nothing about the common difference of these progressions. In fact, Beck
\cite{beck1980} showed that there exists a 2-coloring of $\mathbb{N}$ such that
for all large $d$, there do not exist large monochromatic arithmetic progressions
with common difference $d$ --- in fact if $P$ is a monochromatic arithmetic
progression with common difference $d$, then $|P|<2\log d$.
In the opposite direction, there exists a 2-coloring of $\mathbb{N}$ for which
there does not even exist a monochromatic 4-term arithmetic progression $\{a,
a+d,a+2d,a+3d\}$ with $d>a/3$. (The 1/3 here cannot be replaced by 1/32.)
See \cite{brown+landman1999}.
The next theorem, first proved in \cite{brown1968} (see also \cite{brown1971-1}), shows
that one can control the common difference, but at the expense of not
insisting on an arithmetic progression.
\begin{thrm}\label{t11-6} for every finite coloring of $N$, there exist a
fixed $d$ and arbitrarily large monochromatic sets $A=\{a_1