\documentclass[11pt]{article}
\textwidth=6.25in
\textheight=9.0in
\topmargin=10pt
\headsep=25pt
\parskip=10pt
\oddsidemargin=10pt
\evensidemargin=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9


\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}{Definition}[section]


\usepackage{latexsym}
\usepackage{amssymb}


\begin{document}
\begin{center}
{\bf MONOCHROMATIC FORESTS OF FINITE SUBSETS OF
$\mathbf{N}$}
\vskip 20pt
{\bf Tom C. Brown}\\
{\smallit Department of Mathematics and Statistics,
Simon Fraser University,
Burnaby, BC Canada V5A 1S6}\\
{\tt tbrown@sfu.ca}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 2/3/00, Revised: 2/29/00, Accepted: 3/28/00,
Published: 5/19/00}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
It is known that if $N$ is finitely colored, then some color class is
piecewise syndetic. (See Definition 1.1 below for a definition of piecewise
syndetic.) We generalize this result by considering finite colorings of the
set of all finite subsets of $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.


\pagestyle{myheadings}
\markright{{\smalltt INTEGERS:
\smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY
\smalltt 0 (2000), \#A04 \hfill}}

\thispagestyle{empty}
\baselineskip=15pt

\section*{\normalsize 1. Introduction}

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

We first give several basic definitions and facts.

\noindent
{\bf Definition 1.1}
A subset $X$ of $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\textit{\ 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$.)

\noindent
{\bf Definition 1.2}
A subset $X$ of $N$ has\emph{\ property AP} if there are arbitrarily large
(finite) sets $A\subset X$ such that $A$ is an arithmetic progression.

\begin{description}
\item[Fact 1]  If $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 Fact 1 appear in
[2], [3], [7].) However, Fact 1 neither implies, nor is implied by, van der
Waerden's theorem.


\item[Fact 2]  If $X\subseteq N$ and $X$ has positive upper density, then
has property AP (by Szemer\'{e}di's theorem) but need not be piecewise
syndetic. (For an example, see [1].)
\end{description}

%\vskip 10pt
%\footnoterule
%\noindent
%{\footnotesize Subject Class:  Primary 11B25; Secondary 05D10,
%keywords:  piecewise syndetic, van der Waerden's theorem, arithmetic
%progression, tree, forest}

The finite version of Fact 1 is:



\noindent
{\bf Theorem 1.1 }{\it
For all $r\geq 1$ and $f\in N^{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$.}


\noindent
{\it 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$ 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))$.
{\hfill $\Box$}

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 [10]).

In [8] it is shown that there is a 2-coloring $\chi $ of $N$ and a function $%
f\in N^{N}$ such that if $A=\{a,a+d,a+2d,\cdots \}$ is any $\chi $%
-monochromatic arithmetic progression, then $|A|<f(d)$. Hence one cannot
require the monochromatic set $A$ in Theorem 1.1 to be an arithmetic
progression.

In this note we generalize Theorem 1.1 by considering finite colorings of $%
P([1,n])$ and of $P_{f}(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*{\normalsize 2. $d$-copies Of Finite Rooted Forests}

Theorem 2.1 below is a generalization of Theorem 1.1. To state Theorem 2.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\wedge y$ for the greatest lower bound of $x,y$, if it exists. (Thus $%
x\wedge y$ exists if and only if $x,y$ are vertices of some tree $T$ in $F$,
and then $x\wedge y$ is the common ancestor of $x$ and $y$ which has
greatest height, that is, is furthest from the root of $F$.)

\noindent
{\bf Definition 2.1}
Let $F$ be a rooted forest, and let $d\geq 1$. (This definition applies to
both finite and infinite rooted forests $F$.) A \emph{d-copy} of $F$ in $%
P([1,n])$ (resp $P_{f}(N)$) is a subset $S$ of $P([1,n])$ (resp $P_{f}(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{itemize}
\item  1. $x\leq y\Leftrightarrow \phi (x)\subseteq \phi (y)$

\item  2. If $x\wedge y$ exists, then $\phi (x\wedge y)=$ $\phi (x)\cap \phi
(y)$

\item  3. If $x,y$ belong to different trees of $F,$ then $\phi (x)\cap \phi
(y)=\emptyset $.

\item  4. 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{itemize}

\noindent
{\bf Theorem 2.1 }{\it
For all $r\geq 1$ and $f\in N^{N}$, there exists (a smallest) $
n^{*}=n^{*}(f,r)$ such that whenever $P([1,n^{*}])$ is $r$-colored, there
exist $d\geq 1$ and monochromatic $d$-copies (all in the same color) of all
rooted forests having $f(d)$ vertices. Furthermore, $n^{*}(1)=f(1)$ and $
n^{*}(f,r+1)\leq n^{*}(f,r)\cdot f(n^{*}(f,r))$.}


\noindent
{\it 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\geq 1$, 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\geq 1$, 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)])$.

\noindent
{\bf Case 1.} For some $s,0\leq s\leq f(m)-1$, there is $A\subseteq [1,sm]$ (for
$% s=0$ we use $A=\emptyset $) such that the coloring $\chi ^{\prime }$ on $
P([sm+1,(s+1)m])$ defined by $\chi ^{\prime }(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\geq
1$ and a fixed color $i,1\leq i\leq r$, such that every rooted forest with $
f(d)$ vertices has a $\chi ^{\prime }$-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.

\noindent
{\bf 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},\cdots 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
^{\prime }$ on $P([tm+1,(t+1)m])$ by setting $\chi ^{\prime }(B)=\chi
(B_{1}\cup B),$ $B\subseteq [tm+1,(t+1)m]$. Since Case 1 does not occur, $%
\chi ^{\prime }$ takes on the value $r+1$, say $r+1=\chi ^{\prime
}(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.
{\hfill $\Box$}

It is straightforward to show that Theorem 1.1 implies Fact 1. In the same
way, it is straightforward to show that Theorem 2.1 implies the following
result.

\noindent
{\bf Theorem 2.2 }{\it
Let $P_{f}(N)$ be finitely colored. Then there exists a fixed $d\geq 1$ such
that for every finite forest $F$, there is a monochromatic $d$-copy of $F$.
}

\section*{\normalsize 3. $d$-copies Of $\omega $-forests}

In this section, we show that a result considerably stronger than Theorem
2.2 can be proved by using Ramsey's theorem together with Fact 1.

\noindent
{\bf Theorem 3.1 }{\it
Let $P_{f}(N)$ be finitely colored. Then for some fixed $d\geq 1$ there
exist arbitrarily large (finite) sets $A=\{a_{0}<a_{1}<\cdots
<a_{n}\}\subset N$ with $a_{j+1}-a_{j}\leq d,0\leq j\leq n-1$, and infinite
sets $Y\subseteqq 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$.
}

\noindent
{\it Proof.}
Let $g$ be a given finite coloring of $P_{f}(N)$. Using Ramsey's theorem,
let $N=X_{0}\supseteqq X_{1}\supseteqq \cdots \supseteqq X_{m}\supseteqq
\cdots $ be a sequence of infinite sets such that for each $m\geq 1$, $g$ is
constant on the set $[X_{m}]^{m}$ of all $m$-element subsets of $X_{m}$.
Define the finite coloring $h$ of $N$ by setting $h(m)=g(A)$, where $A$ is
any $m$-element subset of $X_{m}$.

By Fact 1 above, there is some $i$ such that $h^{-1}(i)$ is a piecewise
syndetic set. This means that there is a fixed $d\geq 1$ 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}\}$ be 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}}\supseteqq X_{a_{1}}\supseteqq
X_{a_{2}}\supseteqq \cdots \supseteqq 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}}$.
{\hfill $\Box$}

\noindent
{\bf Definition 3.1}
An $\omega $\emph{-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$.


\noindent
{\bf Corollary 3.2 }{\it
Let $P_{f}(N)$ be finitely colored. Then there exists a fixed $d\geq 1$ such
that for every $n\geq 1$, there is a monochromatic $d$-copy of an $\omega $%
-forest of height $n.$}


\noindent
{\it Proof.}
Let $d$ be as in the conclusion of Theorem 3.1, and let $n$ be given. From
Theorem 3.1, let $A=\{a_{0}<a_{1}<\cdots <a_{n}\}\subset 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 \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=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},\cdots ,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_{i}p_{j},p_{i}p_{j}^{2},p_{i}p_{j}^{3},%
\cdots ,p_{i}p_{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_{i}p_{j}p_{k},p_{i}p_{j}p_{k}^{2},p_{i}p_{j}p_{k}^{3}$, $\cdots
,p_{i}p_{j}p_{k}^{a_{2}-a_{1}}\}$. Continue in this way until an $\omega $
-forest of height $n$ is obtained.
{\hfill $\Box$}

\section*{\normalsize 4. 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
3.1, except that now the set $A$ will be an arithmetic progression.

\noindent
{\bf Theorem 4.1 }{\it
Let $P_{f}(N)$ be finitely colored. Then for every $n\geq 1$ there exist an
arithmetic progression $\{a,a+d,a+2d,\cdots 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.
}

\noindent
{\it Proof.}
The proof is essentially the same as the proof of Theorem 3.1. Let $g$ be a
given finite coloring of $P_{f}(N)$. Using Ramsey's theorem, let $%
N=X_{0}\supseteqq X_{1}\supseteqq \cdots \supseteqq X_{m}\supseteqq \cdots $
be a sequence of infinite sets such that for each $m\geq 1$, $g$ is constant
on the set $[X_{m}]^{m}$ of all $m$-element subsets of $X_{m}$. Define the
finite coloring $h$ of $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\geq 1$
there is an $h$-monochromatic set $\{a,a+d,a+2d,\cdots a+(n-1)d\}$. Hence,
as in the proof of Theorem 3.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}$.
{\hfill $\Box$}

\noindent
{\bf Definition 4.1}
Let $F$ be a rooted forest. An \emph{arithmetic copy} of $F$ in $P([1,n])$
(resp $P_{f}(N)$) is a subset $S$ of $P([1,n])$ (resp $P_{f}(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{itemize}
\item  1. $x\leq y\Leftrightarrow \phi (x)\subseteq \phi (y)$

\item  2. If $x\wedge y$ exists, then $\phi (x\wedge y)=$ $\phi (x)\cap \phi
(y)$

\item  3. If $x,y$ belong to different trees of $F,$ then $\phi (x)\cap \phi
(y)=\emptyset $.

\item  4. If $x$ is any root of $F$, then $|\phi (x)|=a$.

\item  5. If $y$ covers $x$ then $|\phi (y)|-|\phi (x)|=d$.
\end{itemize}

\noindent
{\bf Corollary 4.2 }{\it
Let $P_{f}(N)$ be finitely colored. Then for every $n\geq 1$ there exists a
monochromatic arithmetic copy of an $\omega $-forest of height $n$.
}

\noindent
{\it Proof.}
Using Theorem 4.1,the monochromatic arithmetic copy of an $\omega $-forest
of height $n$ can be constructed just as in the proof of Corollary 3.2.
{\hfill $\Box$}

\noindent
{\bf Corollary 4.3 }{\it
For all $r\geq 1$ and $k\geq 1$ , there exists (a smallest) $%
w^{*}=w^{*}(k,r) $ such that whenever $P([1,w^{*}]$ is $r$-colored, there
exist $a\geq 1$ and $d\geq 1$ 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,\cdots $ has size $a+jd$.
}

\noindent
{\it Proof.}
This follows from Corollary 4.2 by a compactness argument. (It could also be
proved directly, using the finite forms of Ramsey's theorem and van der
Waerden's theorem.)
{\hfill $\Box$}

\section*{\normalsize 5. Remarks And Open Questions}

Piecewise syndetic sets are discussed at length in [5] and [6].

Howard Straubing [10] has used Theorem 1.1 to give new proofs (which are
almost entirely combinatorial) of all of the key 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$-ary operations,
perhaps Theorem 2.1 may have some applications to algebra.

The proof of Theorem 4.1, although found independently from [9], combines
van der Waerden's theorem and Ramsey's theorem in the same way these were
combined in the proof of Theorem 2 in [9]. Some related results, and
additional references, can be found in [11] and [12].

It was observed by J. Walker, as reported in [13], that if $k\geq 1$ and $%
\varepsilon >0$ are given, then for sufficiently large $n$, if $S\subseteq
P([1,n])$ and $|S|>\varepsilon |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 [4], p. 17.)

\section*{\normalsize References}

\noindent
[1]  V. Bergelson, N. Hindman, R. McCutcheon, Notions
of size and combinatorial properties of quotient sets in semigroups,
Topology Proc., to appear.

\noindent
[2]  T.C. Brown, On locally finite semigroups (in Russian),
Ukraine Math. J. 20 (1968), 732-738.

\noindent
[3]  T.C. Brown, An interesting combinatorial method in the
theory of locally finite semigroups, Pacific J. Math. 36 (1971), 285-289.

\noindent
[4]  Paul Erd\"{o}s and R. L. Graham, Old and New
Problems and Results in Combinatorial Number Theory, L'Enseignement
Math\'{e}matique, Gen\`{e}ve, 1980.

\noindent
[5]  H. Furstenberg, Recurrence in Ergodic Theory and
Combinatorial Number Theory, Princeton University Press, Princeton, 1981.

\noindent
[6]  N. Hindman and D. Strauss, Algebra in the Stone
-\v {C}ech Compactification, Walter de Gruyter, Berlin, New York, 1998.

\noindent
[7]  G. Jacob, La finitude des repr\'{e}sentations lin\'{e}aires
des semi-groupes est d\'{e}cidable, J. Algebra 52 (1978), 437-459.

\noindent
[8]  J. Justin, Th\'{e}or\`{e}m de van der Waerden, Lemme de
Brown et demi-groups r\'{e}p\'{e}titifs, ''Journ\'{e}es sur la Th\'{e}orie
Alg\'{e}brique des Demi-groups (1971),'' Facult\'{e} de Sciences de Lyon.

\noindent
[9]  J. Ne\v {s}et\v {r}il, V. R\"{o}dl, Combinatorial
partitions of finite posets and lattices - Ramsey lattices, Algebra
Universalis 19 (1984), 106-119.

\noindent
[10]  H. Straubing, The Burnside problem for semigroups of
matrices, in Combinatorics on Words, Progress and Perspectives, Academic
Press 1982, 279-295.

\noindent
[11]  C.J. Swanepoel, L.M. Pretorius, A van der Waerden
theorem for trees, Bull. ICA 21 (1997), 108-111.

\noindent
[12]  C.J. Swanepoel, L.M. Pretorius, Upper Bounds for a
Ramsey Theorem for Trees, Graphs and Combin. 10 (1994), 377-382.

\noindent
[13]  W.T. Trotter, P. Winkler, Arithmetic Progressions in
Partially Ordered Sets, Order 4 (1987), 37-42.


\end{document}