%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-19/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{defn}{Definition}
\newtheorem{fact}{Fact}
\theoremstyle{remark}
\newtheorem*{qstn}{Question}
\newtheorem*{rmrk}{Remark}

\theoremstyle{namedthrm}
\newtheorem{thrm}{Theorem}

\title{Monochromatic Arithmetic Forests}
\author{Tom C. Brown\footnote{Department of Mathematics and Statistics,
ÓÈÎïÊÓƵ, Burnaby, British Columbia, V5A 1S6, Canada.
\texttt{tbrown@sfu.ca}}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Monochromatic arithmetic forests}, Paul Erdos and His
  Mathematics (A.~Sali, M. Simonovits, and V.T. S\'os, eds.), Janos Bolyai
  Mathematical Society, Budapest, Hungary, 1999, pp.~42--44.}\bigskip\end{center}

\begin{defn}\label{d1} If $A = \{a_1<a_2<\cdots<a_n\} \subset \mathbb{N}$,
where $\mathbb{N}$ is the set of positive integers, we say that the \emph{
gap size} of $A$ is $\gs(A) = \max\{a_{j+1} - a_j:1\leq j \leq n - 1\}$.
(If $|A| = 1$, set $\gs(A) = 1$.)\end{defn}
\begin{defn}\label{d2} A subset $X$ of $\mathbb{N}$ is \emph{piecewise
syndetic} if for some \emph{fixed} $d\geq1$ there are arbitrarily large
(finite) sets $A\subset X$ such that $\gs(A)\leq d$.\end{defn}
\begin{defn}\label{d3} A subset $X$ of $\mathbb{N}$ has \emph{property AP}
if there are arbitrarily large (finite) sets $A\subset X$ such that $A$
is an arithmetic progression.\end{defn}
\begin{fact}\label{f1} If $\mathbb{N} = X_1\cup X_2\cup\cdots\cup X_n$
then some $X_i$ is piecewise syndetic (and hence also has property AP).
(The first proofs of Fact \ref{f1} appear in \cite{brown1968,brown1971-1,
jacob1978}.) However, this result neither implies, nor is implied by,
van der Waerden's theorem on arithmetic progressions.\end{fact}
\begin{fact}\label{f2} If $X\subset\mathbb{N}$ and $X$ has positive upper
density, then $X$ has property AP (by Szemer\'edi's theorem) but $X$ need
not be piecewise syndetic. (For an example, see
\cite{bergelson+hindman+mccutcheon1998}.)\end{fact}

The finite version of Fact \ref{f1} is:

\begin{thrm}[A] \namedthmlabel{tA} For all $r\geq1$ and $f\in\mathbb{N}^\mathbb{N}$, there
exists $n = n(f,r)$ such that whenever $[1,n]$ is $r$-colored, there is
a monochromatic set $A$ such that $|A|\geq f(\gs(A))$. (Furthermore,
$n(f,1) = f(1) + 1$ and $n(f,r+1) \leq (r+1)f(n(f,r)) + 1$.)\end{thrm}

There are applications of this result to the theory of locally finite
semigroups, and in particular to Burnside's problem for semigroups of
matrices (see \cite{straubing1982}).

The main result of this note is the following generalization of Theorem
\ref{tA}:

\begin{thrm}[A*]\namedthmlabel{tA*} For all $r\geq1$ and $f\in\mathbb{N}^\mathbb{N}$,
there exists $n^* = n^*(f,r)$ such that whenever $P([1,n^*])$ (the set of all
subsets of $[1,n^*]$) is $r$-colored, there exist $d\geq1$ and monochromatic
copies (all in the same color) of all rooted forests having $f(d)$ vertices.
These monochromatic copies have the property that for all pairs of vertices
$x,y$, if vertex $y$ covers vertex $x$, then $|y| - |x|\leq d$. Also, if
$x,y$ belong to the same tree then $x\land y = x\cap y$; if $x,y$ belong to
different trees then $x\cap y = \varnothing$. (Furthermore, $n^*(f,1) = f(1)$
and $n^*(f,r+1)\leq n^*(f,r)\cdot f(n^*(f,r))$.)\end{thrm}

(The same remarks concerning $x\cap y$ apply to all of the following results.)

One can prove a similar variation of van der Waerden's theorem:

\begin{thrm}[W*]\namedthmlabel{tW*} For all $r\geq1$ and $k\geq1$, there exists
$w^* = w^*(k,r)$ such that whenever $P([1,w^*])$ is $r$-colored, there exist
$a\geq1$ and $d\geq1$ and monochromatic copies (all in the same color) of all
rooted forests having $k$ vertices. These monochromatic copies have the property
that every vertex at level $i=0,1,\ldots$ has size $a+id$.\end{thrm}

The proof of Theorem \ref{tW*} uses van der Waerden's theorem and the finite
Ramsey's theorem, in essentially the same way these were combined in the proof
of Theorem 2 in \cite{nesetril+rodl1984}. The results that follow use the infinite
Ramsey's theorem together with respectively Fact \ref{f1}, van der Waerden's
theorem, and the Erd\H{o}s-Graham canonical van der Waerden's theorem.

\begin{defn} An \emph{$\omega$-tree of height $n$} is a rooted tree in which
every maximal chain has $n+1$ vertices, and every non-maximal vertex has
$\omega$ immediate succesors. An \emph{$\omega$-forest of height $n$} is a
union of $\omega$ pairwise disjoint $\omega$-trees of height $n$.\label{d4}
\end{defn}
\begin{defn}\label{d5} An \emph{arithmetic forest in $[\mathbb{N}]^{<\omega}$}
(the set of all finite subsets of $\mathbb{N}$) is a forest for which there
exist $a\geq1$, $d\geq1$ such that all vertices at level $i$ have size $a+id$,
$i\geq0$.\end{defn}

\begin{thrm}[A**]\namedthmlabel{tA**} Let $[\mathbb{N}]^{<\omega}$ be
finitely colored. Thene there exists a \emph{fixed} $d\geq1$ such that
for every $n\geq1$, there is a monochromatic $\omega$-forest $F(n)$ of
height $n$ such that for all pairs of vertices $x,y$ in $F(n)$, if $y$
covers $x$ then $|y|-|x|\leq d$.\end{thrm}
\begin{thrm}[W**]\namedthmlabel{tW**} Let $[\mathbb{N}]^{<\omega}$ be
finitely colored. Then for every $n\geq1$ there exists a monochromatic
arithmetic $\omega$-forest $F(n)$ of height $n$.\end{thrm}
\begin{thrm}[C**]\namedthmlabel{tC**} Let $[\mathbb{N}]^{<\omega}$ be
$\omega$-colored. Then for every $n\geq1$ there exists an arithmetic
$\omega$-forest $F(n)$ of height $n$ such that either $F(n)$ is
monochromatic or there are distinct colors $c_0,\ldots,c_n$ such that
all vertices at level $i$ have color $c_i$, $0\leq i\leq n$.\end{thrm}

\begin{qstn} It was observed by J. Walker in \cite{trotter+winkler1987}
that if $k\geq1$ and $\epsilon>0$ are given, then for sufficiently large
$n$, if $S\subseteq P([1,n])$ and $|S| > \epsilon|P([1,n])|$, $S$ must
contain an arithmetic chain of length $k$. Is it true that for
sufficiently large $n$, if $S\subseteq P([1,n])$ and $|S|>\epsilon
|P([1,n])|$, $S$ must contain arithmetic copies of all $k$-vertex
rooted forests?\end{qstn}

\begin{rmrk} Some related results, and additional references, can be
found in \cite{swanepoel+pretorius1997} and \cite{swanepoel+pretorius1994}.
\end{rmrk}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}