%%%% 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, Simon Fraser University, 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|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}