%%%% 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, 91泡芙, 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}