%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-15/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}[section]
\newtheorem{corl}[thrm]{Corollary}
\newtheorem{defn}{Definition}[section]
\newtheorem{fact}{Fact}

\title{Monochromatic Forests of Finite Subsets of $\mathbb{N}$ }
\author{Tom C. Brown\footnote{Department of Mathematics and Statistics, ¶¡ÏãÔ°AV, Burnaby, BC Canada V5A 1S6.
\texttt{tbrown@sfu.ca}.}}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Monochromatic forests of finite subsets of $N$}, INTEGERS -
  Elect. J. Combin. Number Theory \textbf{0} (2000), A4.}\bigskip\end{center}

\begin{abstract}It is known that if $\mathbb{N}$ is finitely colored, then some
color class is piecewise syndetic. (See Definition~\ref{d1-1} below for a
definition of piecewise syndetic.) We generalize this result by considering
finite colorings of the set of all finite subsets of $\mathbb{N}$. The
monochromatic objects obtained are ``$d$-copies'' of arbitrary finite
forests and arbitrary infinite forests of finite height. van der Waerden's
theorem on arithmetic progressions is generalized in a similar way. Ramsey's
theorem and van der Waerden's theorem are used in some of the proofs.
\end{abstract}

\section{Introduction}

$\mathbb{N}$ denotes the set of positive integers, and $[1,n]$ denotes the set
$\{ 1,2,\ldots, n\}$. $P_f(\mathbb{N})$ denotes the set of all finite
subsets of $\mathbb{N}$, and $P([1,n])$ denotes the set of all subsets
of $[1,n]$.

We first give several basic definitions and facts.

\begin{defn}\label{d1-1} A subset $X$ of $\mathbb{N}$ is \emph{piecewise
syndetic} if for some fixed $d$ there are arbitrarily large (finite) sets
$A\subset X$ such that $\gs(A) \leq d$, where $\gs(A)$, the gap size of
$A = \{a_1 < a_2 < \cdots < a_n \}$, is defined by $\gs(A) = \max\{a_{j+1}
-a_j:1\leq j \leq n - 1 \}$. (If $|A| = 1$, we set $\gs(A) = 1$.)\end{defn}
\begin{defn}\label{d1-2} 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} 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, by van der
Waerden's theorem on arithmetic progressions). (The first proofs of this
fact appear in \cite{brown1968,brown1971-1,jacob1978}.) However, the fact
neither implies, nor is implied by, van der Waerden's theorem.\label{f1}
\end{fact}

\begin{fact} If $X\subseteq\mathbb{N}$ and $X$ has positive upper density,
then $X$ has property AP (by Szemer\'edi's theorem) but 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} For all $r\geq1$ and $f\in\mathbb{N}^\mathbb{N}$, there exists
(a smallest) $n = n(f,r)$ such that whenever $[1,n]$ is $r$-colored, there
is a monochromatic set $A$ such that $|A| > f(\gs(A))$. Furthermore, $n(f,1)
= f(1) + 1$ and $n(f,r+1)\leq(r+1)f(n(f,r))+1$.\label{t1-1}\end{thrm}
\begin{proof} We use induction on $r$. For $r=1$, it's clear that $n(f,1)
= f(1) + 1$, for then $A = [1, f(1) + 1]$ is monochromatic, and $|A|>f(1)
= f(\gs(a))$.

Suppose that $n(f,r)$ exists, and assume without loss of generality that $f$
is non-decreasing. Let an $(r+1)$-coloring of $[1,n]$ be given, such that
for every monochromatic set $A\subseteq[1,n]$, $|A|\leq f(\gs(A))$. We'll
show that under these conditions $n\leq (r+1)f(n,f,r))$, from which it
follows that $n(f,r+1)\leq (r+1)f(n(f,r))+1$.

Now if $B = [a,b] \subseteq[1,n]$ misses the color $j$, then by the induction
hypothesis (applied to the interval $[a,b]$ instead of the interval $[1,b-a+1]$)
and our assumption about the given coloring, $|B| = b-a+1 \leq n(f,r) - 1$.

Hence if $A(j) = \{x\in [1,n] :x \text{ has color } j\}$, then $\gs(A(j))
\leq (b+1) - (a - 1)\leq n(f,r)$. Therefore (again by our assumption about
the given coloring) $|A(j)| \leq f(\gs(A(j))) \leq f(n(f,r))$.

Finally, $n = \sum |A(j)| \leq (r + 1)f(n(f,r))$.\end{proof}

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}).

In \cite{nesetril+rodl1984} it is shown that there is a 2-coloring $\chi$
of $\mathbb{N}$ and a function $f\in\mathbb{N}^\mathbb{N}$ such that if
$A = \{ a,a+d,a+2d,\ldots\}$ is any $\chi$-monochromatic arithmetic
progression, then $|A|<f(d)$. Hence one cannot require the monochromatic
set $A$ in Theorem \ref{t1-1} to be an arithmetic progression.

In this note we generalize Theorem \ref{t1-1} by considering finite colorings
of $P([1,n])$ and of $P_f(\mathbb{N})$. We also generalize van der Waerden's
theorem on arithmetic progressions. (We use van der Waerden's theorem in the
proof, as well as Ramsey's theorem.) We conclude with several open questions.

\section{$d$-Copies of Finite Rooted Forests}

Theorem \ref{t2-1} below is a generalization of theorem \ref{t1-1}. To state
Theorem \ref{t2-1}, we need some additional terminology.

Let $F$ be any finite rooted forest, by which we mean a union of pairwise
disjoint rooted trees. We regard $F$ as a partially ordered set in the natural
way. This means that the roots of the trees in $F$ are the minimal elements of
$F$, and for vertices $x,y$ of $F$, $x\leq y$ means that in some tree $T$ in
$F$, $x$ is an ancestor of $y$, that is, the unique path from the root of
$T$ to $y$ contains $x$. For vertices $x,y$ of $F$, we write $x\land y$
for the greatest lower bound of $x,y$, if it exists. (Thus $x\land y$ exists
if and only if $x,y$ are vertices of some tree $T$ in $F$, and then $x\land y$
is the common ancestor of $x$ and $y$ which has greatest height, that is,
is furthest from the root of $T$.)

\begin{defn} Let $F$ be a rooted forest, and let $d\geq1$. (This definition
applies to both finite and infinite rooted forests $F$.) A $d$-copy of $F$
in $P([1,n])$ (resp $P_f(\mathbb{N})$) is a subset $S$ of $P([1,n])$ (resp
$P_f(\mathbb{N})$) for which there exists a bijection $\phi$ from the vertex
set of $F$ to $S$ such that for all vertices $x,y$ of $F$,
\begin{enumerate}
\item $x\leq y \Leftrightarrow \phi(x)\subseteq \phi(y)$
\item If $x\land y$ exists, then $\phi(x\land y) = \phi(x)\cap\phi(y)$.
\item If $x,y$ belong to different trees of $F$, then $\phi(x)\cap\phi(y) = \varnothing$.
\item If $y$ covers $x$ then $|\phi(y)| - |\phi(x)| \leq d$. (We say that $y$
covers $x$ iff $x < y$ and there does not exist $z$ with $x < z < y$.)
\end{enumerate}\end{defn}

\begin{thrm}\label{t2-1} For all $r\geq1$ and $f\in\mathbb{N}^\mathbb{N}$,
there exists (a smallest) $n^* = n^*(f,r)$ such that whenever $P([1,n^*])$
is $r$-colored, there exist $d\geq1$ and monochromatic $d$-copies (all in
the same color) of all rooted forests having $f(d)$ vertices. Furthermore,
$n^*(f,1) = f(1)$ and $n^*(f,r+1)\leq n^*(f,r)\cdot f(n^*(f,r))$.\end{thrm}
\begin{proof} We use induction on $r$. For $r = 1$, we can take $d = 1$,
and then easily construct a 1-copy of any rooted forest with $f(1)$ vertices,
using subsets of $[1,f(1)]$. (For a forest with more than one component, we
need to use all the elements of $[1,f(1)]$.) Therefore $n^*(f,1) = f(1)$.

Now let $r\geq1$, and assume that $n^*(f,r) = m$ exists. We show that $n^*(f,r+1)
\leq mf(m)$.

Let an $(r+1)$-coloring $\chi$ of $P([1,mf(m)])$ be given. We show that either
(Case 1) there is a $d\geq1$, a fixed color $i$, $1\leq i\leq r$, and a fixed
$t$, $1\leq t \leq f(m)$, such that every rooted forest with $f(d)$ vertices
has a $\chi$-monochromatic $d$-copy in the color $i$, contained in $P([1,tm])$,
or else (Case 2) every rooted forest $F$ with $f(m)$ vertices has a $\chi$-monochromatic
$m$-copy in the color $r+1$, contained in $P([1,mf(m)])$.

\paragraph{Case 1.} For some $s$, $0\leq s \leq f(m) - 1$, there is $A\subseteq
[1,sm]$ (for $s = 0$ we use $A =\varnothing$) such that the coloring $\chi'$
on $P([sm+1, (s + 1)m])$ defined by $\chi'(B) = \chi(A\cup B)$, $B\subseteq
[sm + 1, (s+1)m]$, does not use the color $r+1$, and hence is an $r$-coloring.
By the induction hypothesis and the definition of $m$ (using the interval
$[sm+1,(s+1)m]$ instead of the interval $[1,m]$), there is a $d\geq1$ and a
fixed color $i$, $1\leq i\leq r$, such that every rooted forest with $f(d)$
vertices has a $\chi'$-monochromatic $d$-copy in the color $i$, contained
in $[sm+1, (s+1)m]$. By adjoining the set $A$ to each set in this $d$-copy,
we get a $\chi$-monochromatic $d$-copy in the color $i$, contained in $[1,(s+1)m]$.
This finishes Case 1.

\paragraph{Case 2.} Now we assume that Case 1 does not occur, and that $F$ is
an arbitrary rooted forest with $f(m)$ vertices. We show how to construct an
$m$-copy of $F$ in $P([1,mf(m)])$, which is $\chi$-monochromatic in the color
$r+1$.

First, by assumption the color $r+1$ occurs when $\chi$ is restricted to
$P([1,m])$. Assume $\chi(B_1) = r+1$, where $B_1\subseteq[1,m]$. We set
$\phi(x_1) = B_1$, where $x_1$ is a root of $F$.

If $F$ has another root, $x_2$, we set $\phi(x_2) = B_2$, where $B_2\subseteq
[m+1,2m]$ and $\chi(B_2) = r+1$. Similarly, if $x_1,x_2,\ldots,x_t$ are all
the roots of $F$, we define $\phi(x_i) = B_i$, where $B_i\subseteq[(i-1)m+1,
im]$ and $\chi(B_i) = r+1$, $1\leq i \leq t$.

The construction continues as follows. Suppose $y_1$ covers $x_1$ in $F$. Since
$\phi(x_1) = B_1\subseteq[1,tm]$, we make up the coloring $\chi'$ on $P([tm+1,
(t+1)m])$ by setting $\chi'(B) = \chi(B_1\cup B)$, $B\subseteq [tm+1,(t+1)m]$.
Since Case 1 does not occur, $\chi'$ takes on the value $r+1$, say $r+1 =
\chi'(C_1) = \chi(B_1\cup C_1)$, where $C_1\subseteq[tm+1,(t+1)m]$. Then we
set $\phi(y_1) = B_1\cup C_1$, and clearly $|\phi(y_1)| - |\phi(x_1)| = |C_1|
\leq m$.

The construction is continued in the same way. If $y$ covers $x$ in $F$, and
$\phi(x)$ has already been defined but $\phi(y)$ has not, we set $\phi(y) =
\phi(x)\cup C$, where $C$ is some subset of the next unused interval of
length $m$, for which $\chi(\phi(x)\cup B) = r+1$. Since $F$ has $f(m)$
vertices, there are enough intervals of length $m$ to finish the construction.
\end{proof}

It is straightforward to show that Theorem \ref{t1-1} implies Fact \ref{f1}.
In the same way, it is straightforward to show that Theorem \ref{t2-1} implies
the following result.

\begin{thrm}\label{t2-2} Let $P_f(\mathbb{N})$ be finitely colored. Then there
exists a fixed $d\geq1$ such that for every finite rooted forest $F$, there is
a monochromatic $d$-copy of $F$ in $P_f(\mathbb{N})$.\end{thrm}

\section{$d$-Copies of $\omega$-Forests}

In this section, we show that a result considerably stronger than Theorem \ref{t2-2}
can be proved by using Ramsey's theorem along with Fact \ref{f1}.

\begin{thrm}\label{t3-1} Let $P_f(\mathbb{N})$ be finitely colored. Then for
some fixed $d\geq1$ there exist arbitrarily large (finite) sets $A = \{a_0 <
a_1 < \cdots < a_n\} \subseteq \mathbb{N}$ with $a_{j+1} - a_j\leq d$, $0
\leq j \leq n - 1$, and infinite sets $Y\subseteq \mathbb{N}$ ($Y$ depends
on $A$) such that $[Y]^{a_0}\cup [Y]^{a_1}\cup\cdots\cup[Y]^{a_n}$ is
monochromatic, where $[Y]^{a_i}$ denotes the set of all $a_i$-element subsets
of $Y$.\end{thrm}

\begin{proof} Let $g$ be a given finite coloring of $P_f(\mathbb{N})$. Using
Ramsey's theorem, let $\mathbb{N} = X_0 \supseteq X_1 \supseteq \cdots \supseteq
X_m \supseteq \cdots$ be a sequence of infinite sets such that for each $m\geq1$,
$g$ is constant on the set $[X_m]^m$ of all $m$-element subsets of $X_m$. Define
the finite coloring $h$ of $\mathbb{N}$ by setting $h(m) = g(A)$, where $A$ is
any $m$-element subset of $X_m$.

By Fact \ref{f1} above, there is some $i$ such that $h^{-1}(i)$ is a piecewise
syndetic set. This means that there is a fixed $d\geq1$ such that for arbitrarily
large $n$, there are $h$-monochromatic sets $\{a_0 < a_1 < \cdots < a_n\}$ with
$a_{j+1} - a_j\leq d$, $0 \leq j \leq n - 1$.

Let $\{a_0 < a_1 < \cdots < a_n\}$ by such an $h$-monochromatic set. By the
definition of $h$, $g$ is constant on $[X_{a_0}]^{a_0}\cup [X_{a_1}]^{a_1}\cup
[X_{a_2}]^{a_2}\cup\cdots\cup[X_{a_n}]^{a_n}$. Since $X_{a_0}\supseteq X_{a_1}
\supseteq X_{a_2}\supseteq \cdots \supseteq X_{a_n}$, we have that $g$ is
constant on $[Y]^{a_0}\cup [Y]^{a_1}\cup [Y]^{a_2}\cup\cdots\cup[Y]^{a_n}$,
where $Y = X_{a_n}$.\end{proof}

\begin{defn}\label{d3-1} An $\omega$-tree of height $n$ is a rooted tree in
which every maximal chain has $n+1$ vertices, and every non-maximal vertex
has infinitely many immediate successors. An $\omega$-forest of height $n$
is a union of infinitely many pairwise disjoint $\omega$-trees of height
$n$.\end{defn}

\begin{corl}\label{c3-2} Let $P_f(\mathbb{N})$ be finitely colored. Then
there exists a fixed $d\geq1$ such that for every $n\geq1$, there is a
monochromatic $d$-copy of an $\omega$-forest of height $n$.\end{corl}
\begin{proof} Let $d$ be as in the conclusion of Theorem \ref{t3-1}, and
let $n$ be given. From Theorem \ref{t3-1}, let $A = \{a_0 < a_1 < \cdots < a_n\}
\subset\mathbb{N}$ satisfy $a_{j+1}-a_j\leq d$, $0\leq j\leq n-1$, and let
$Y$ be an infinite set such that $[Y]^{a_0}\cup [Y]^{a_1}\cup [Y]^{a_2}\cup\cdots\cup[Y]^{a_n}$
is monochromatic.

Now it is just a matter of constructing an $\omega$-forest $F$ of height
$n$ in which all the roots belong to $[Y]^{a_0}$, and for each $j$, $1\leq
j\leq n$, all the vertices at height $j$ belong to $[Y]^{a_j}$. For then,
if vertex $y$ covers vertex $x$ in the forest $F$, then for some $j$,
$0\leq j\leq n - 1$, $x \in [Y]^{a_j}$, $y\in[Y]^{a_{j+1}}$, and $x\subset
y$, so that $|y| - |x| = a_{j+1} - a_j \leq d$.

One construction of $F$ is the following. Assume without loss of generality that
$Y = \mathbb{N}$, and let $p_1,p_2,\cdots,p_k,\cdots$ be the sequence of primes.
Let the roots of $F$ be the sets $S_i$, $1\leq i$, where $S_i = \{p_i,p_i^2,p_i^3,
\ldots,p_i^{a_0}\}$. For each $1\leq i$, let the vertices which cover the
vertex $S_i$ be the sets $S_i\cup S_{ij}$, $i<j$, where $S_{ij} = \{p_ip_j,
p_ip_j^2,p_ip_j^3,\ldots,p_ip_j^{a_1-a_0}\}$. For each $1\leq i < j$, let the
vertices which cover the vertex $S_i\cup S_{ij}$ be the sets $S_i\cup S_{ij}
\cup S_{ijk}$, $j<k$, where $S_{ijk} = \{ p_ip_jp_k, p_ip_jp_k^2, p_ip_jp_k^3,
\ldots, p_ip_jp_k^{a_2-a_1}\}$. Continue in this way until an $\omega$-forest
of height $n$ is obtained.\end{proof}

\section{Arithmetic Copies of $\omega$-Forests}

In this section, we use Ramsey's theorem together with van der Waerden's theorem
on arithmetic progressions to obtain a result similar to Theorem \ref{t3-1},
except that now the set $A$ will be an arithmetic progression.

\begin{thrm}\label{t4-1} Let $P_f(\mathbb{N})$ be finitely colored. Then for
every $n\geq1$ there exist an arithmetic progression $\{a,a+d,a+2d,\ldots,
a+(n-1)d\}$ and an infinite set $Y$ such that $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}
\cup\cdots\cup[Y]^{a+(n-1)d}$ is monochromatic.\end{thrm}

\begin{proof} The proof is essentially the same as the proof of Theorem \ref{t3-1}.
Let $g$ be a given finite coloring of $P_f(\mathbb{N})$. Using Ramsey's theorem,
let $\mathbb{N} = X_0 \supseteq X_1 \supseteq \cdots \supseteq X_m \supseteq \cdots$
be a sequence of infinite sets such that for each $m\geq1$, $g$ is constant on
the set $[X_m]^m$ of all $m$-element subsets of $X_m$. Define the finite coloring
$h$ of $\mathbb{N}$ by setting $h(m) = g(A)$, where $A$ is any $m$-element subset
of $X_m$.

By van der Waerden's theorem on arithmetic progressions, for every $n\geq1$ there
is an $h$-monochromatic set $\{a,a+d,a+2d,\ldots,a+(n-1)d\}$. Hence, as in the
proof of Theorem \ref{t3-1}, $g$ is constant on $[Y]^a\cup[Y]^{a+d}\cup[Y]^{a+2d}
\cup\cdots\cup[Y]^{a+(n-1)d}$, where $Y = X_{a+(n-1)d}$.\end{proof}

\begin{defn}\label{d4-1} Let $F$ be a rooted forest. An \emph{arithmetic copy}
of $F$ in $P([1,n])$ (resp $P_f(\mathbb{N})$) is a subset $S$ of $P([1,n])$
(resp $P_f(\mathbb{N})$) for which there exist positive integers $a,d$ and a
bijection $\phi$ from the vertex set of $F$ to $S$ such that for all vertices
$x,y$ of $F$,
\begin{enumerate}
\item $x\leq y \Leftrightarrow \phi(x)\subseteq \phi(y)$
\item If $x\land y$ exists, then $\phi(x\land y) = \phi(x)\cap\phi(y)$.
\item If $x,y$ belong to different trees of $F$, then $\phi(x)\cap\phi(y) = \varnothing$.
\item If $x$ is any root of $F$, then $|\phi(x)| = a$.
\item If $y$ covers $x$ then $|\phi(y)| - |\phi(x)| = d$.
\end{enumerate}\end{defn}

\begin{corl}\label{c4-2} Let $P_f(\mathbb{N})$ be finitely colored. Then
for every $n\geq1$ there exists a monochromatic arithmetic copy of an
$\omega$-forest of height $n$.\end{corl}
\begin{proof} Using Theorem \ref{t4-1}, the monochromatic arithmetic copy
of an $\omega$-forest of height $n$ can be constructed just as in the proof
of Corollary \ref{c3-2}.\end{proof}

\begin{corl}\label{c4-3} For all $r\geq1$ and $k\geq1$, there exists (a smallest)
$w^* = w^*(k,r)$ such that whenever $P([1,w^*])$ is $r$-colored, there exist
$a\geq1$ and $d\geq1$ and monochromatic arithmetic copies (all in the same color)
of all rooted forests having $k$ vertices. These monochromatic copies have the
property that every vertex at height $j = 0,1,\ldots$ has size $a+jd$.\end{corl}
\begin{proof} This follows directly from Corollary \ref{c4-2} by a compactness
argument. (It could also bo proved directly, using the finite forms of Ramsey's
theorem and van der Waerden's theorem.)\end{proof}

\section{Remarks and Open Questions}

Piecewise syndetic sets are discussed at length in \cite{furstenberg1981-1,
hindman+strauss1998}.

Howard Straubing \cite{straubing1982} has used Theorem \ref{t1-1} to give new
proofs (which are almost entirely combinorial) of all of the ky theorems dealing
with the local finiteness of semigroups of matrices over an arbitrary field,
and with the local finiteness of subsemigroups of rings satisfying a polynomial
identity. Since trees give a natural way to describe $n$-ay operations, perhaps
Theorem \ref{t2-1} may have some applications to algebra.

The proof of Theorem \ref{t4-1}, although found independently in \cite{nesetril+rodl1984},
combines van der Waerden's theorem and Ramsey's theorem in the same way these
were combined in the proof of Theorem 2 in \cite{nesetril+rodl1984}. Some
related results, and additional references, can be found in \cite{swanepoel+pretorius1997,
swanepoel+pretorius1994}.

It was observed by J. Walker, as reported 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 copy of a path of length $k$. Is it true that $S$ must also contain
arithmetic copies of all $k$-vertex rooted forests?

It would also be of interest to find ``canonical'' versions of the results
above, where the number of colors is arbitrary. (For the canonical version of
van der Waerden's theorem, see \cite{erdos+graham1980}, p. 17).


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