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