%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-56/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{cor}{Corollary}
\newtheorem*{lemma}{Lemma}
\newtheorem*{thmV}{Theorem V (Van der Waerden [12])}
\newtheorem*{thmVV}{Theorem V' (Variation)}
\newtheorem*{thmR}{Theorem R}
\newtheorem*{thmRR}{Theorem R' (Ramsey [9])}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remark}
\newtheorem*{fact}{Fact}

\title{Variations on van der Waerden's and Ramsey's Theorems}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Variations on van der Waerden's and Ramsey's theorems},
  Amer. Math. Monthly \textbf{82} (1975), 993--995.}\bigskip\end{center}

\section{Van der Waerden's Theorem} \label{sec: 1}

The particular variation of van der Waerden's Theorem to be presented here has been discovered independently by any number of people, but a proof of its equivalence to van der Waerden's Theorem has, to the author's knowledge, never appeared in print. (The variation is stated in~\cite{rabung1970}, and a recent application will appear in~\cite{mendelsohn1974}.)

\begin{thmV} 
For all positive integers $k$ and $l$ there exists $n = n(k,l)$ such that if any set of $n$ consecutive integers is partitioned into $k$ subsets, at least one of these subsets contains an arithmetic progression of length $l$.
\end{thmV}

\begin{thmVV} 
For all positive integers $m$ and $l$ there exists $p = p(m,l)$ such that if $a_1<a_2<\cdots<a_p$ are positive integers such that $a_{j + 1} - a_j \leq m$, $ 1 \leq j \leq p- 1$, then $\{a_1,\dots,a_p\}$ contains an arithmetic progression of length $l$.
\end{thmVV}

Most published proofs of van der Waerden's theorem are carried out by induction on $k$ and $l$. It wuld be of interest to find a direct inductive proof of Theorem V'. In this note, however, we shall show that Theorem V implies Theorem V' and conversely.

To this end, it is convenient to let $V(k,l)$ denote the statement that if the set $N$ of all positive integers is partitioned into $k$ subsets, then at least one of these subsets contains an arithmetic progression of length $l$. Also, let $V'(m,l)$ denote the statement that if $a_1<a_2<\dots$ are a sequence of positive integers such that $a_{j+1} - a_j \leq m$, $j = 1,2,\dots,$ then the set $\{a_1,a_2,\dots\}$, contains an arithmetic progression of length $l$.

Clearly Theorem V implies statement $V(k,l)$ for every $k$ and $l$, and Theorem V' implies statement $V'(m,l)$ for every $m$ and $l$. We show now that for every $k$ and $l$, $V(k,l)$ implies the existence of $n(k,l)$. Indeed, suppose that the integer $n = n(k,l)$ does not exist. Then for every $n$ we have a sequence of length $N$ on $k$ symbols which represents a partition of $\{1,2,\dots, n\}$ into $k$ subsets such that no subset contains a progression of length $l$.

Let $a_1$ be one of the $k$ symbols which is the $1$st symbol of infinitely many of these sequences. Let $a_2$ be a symbol which is the 2nd symbol of infinitely many sequences beginning with $a_1$. Let $a_3$ be the 3rd symbol of infinitely many sequences starting with $a_1a_2$. In this way we construct an infinite sequence $a_1a_3 \cdots $ on $k$ symbols which represents a partition of $N$ into $k$ subsets, none of which contains an arithmetic progression of length $l$, contradicting $V(k,l)$. (A similar argument shows that $V'(m,l)$ implies the existence of $p(m,l)$. However, this fact will not be used here.)

We are now ready to show that Theorem V' implies Theorem V. We fix $l$ and demonstrate the existence of $n(k,l)$ by induction on $k$. The case $k = 1$ is trivial, so we assume that $n(k,l)$ exists and use this to establish $V(k + 1,l)$, which, as noted above, implies the existence of $n(k + 1,l)$, thus completing the induction.

Hence, let $N$ be partitioned into $k + 1$ subsets and consider the $(k + 1)st$ subset $\{a_1,a_2,\dots\}$. We may as well assume it is infinite. If for some $m$, $a_{j + 1} - a_j \leq m$, $j = 1,2,\dots,$ then by $V'(m,l)$ (which holds since we are assuming Theorem V') the $(k + 1)$st subset contains an arithmetic progression of length $l$. If no such $m$ exists, then the given partition of $N$ induces partitions of arbitrarily large sets of consecutive positive integers into $k$ subsets only. But then by the existence of $n(k,l)$, at least one of these subsets contains an arithmetic progression of length $l$. Thus at least one of the $k + 1$ subsets into which $n$ was partitioned contains an arithmetic progression of length $l$. This establishes $V(k + 1, l)$, and as previously remarked, completes the induction. 

Conversely, we now show that Theorem V implies Theorem V'. Let $m,l$ be given, and let $p = n(m,l) - (m-1)$. Let $A_0 = \{a_1,a_2,\dots,a_p\}$, where $a_1<a_2<\cdots < a_p$ and $a_{j + 1} - a_j \leq m$, $1 \leq j \leq p - 1$. We show $A_0$ contains an arithmetic progression of length $l$. Define
\begin{align*} 
A_1 &= \{a_1 + 1, a_2 + 1, \dots, a_p + 1\} \setminus A_0, \\
A_2 &= \{a_1 + 2, a_2 + 2, \dots, a_p + 2\} \setminus (A_0 \cup A_1), \cdots, \\
A_{m-1} &= \{a_1 + m - 1, a_2 + m - 1, \dots, a_p + m - 1 \} \setminus (A_0 \cup A_1 \cup \cdots \cup A_{m-2}). \end{align*}
Then $\{1,2,\dots,a_p + m - 1\}$ is partitioned into the $m$ sets $A_0,A_1,\dots,A_{m-1}$. Since $a_p + m - 1 \geq p + m - 1 = n(m,l),$ at least one of these sets, say $A_i$, contains an arithmetic progression of length $l$. Since 
\[ A_i \subset \{a_1 + i, a_2 + i, \dots, a_p + i\}, \]
the set $A_0 = \{a_1,a_2,\dots,a_p\}$ also contains such a progression.

This completes the proof of the equivalence of Theorems V and V'.

\section{Ramsey's Theorem} \label{sec: 2}

Let $G$ be a graph with an infinite number of vertices such that at least two of every three vertices of $G$ are joined by an edge of $G$. G. Szekeres (\cite{turan1941},\cite{turan1954}) showed that such a graph $G$ must contain an infinite complete subgraph. (An infinite complete subgraph of $G$ is an infinite set of vertices of $G$, \emph{every} two of which are joined by an edge of $G$.)

P. Tur\'{a}n (\cite{turan1941},\cite{turan1954}) generalized this result by showing that for every fixed positive integer $d$, if $G$ is a graph with an infinite number of vertices such that at least two of every $d$ vertices of $G$ are joined by an edge of $G$, then $G$ contains an infinite complete subgraph.

This result of Tur\'{a}n can itself be further strengthened to obtain the following result, which is designated Theorem R', since it is a ``variation" on Ramsey's Theorem.

\begin{thmRR} Let $G$ be a graph with an infinite number of vertices such that at least two of every \emph{infinite} set of vertices of $G$ are joined by an edge of $G$. Then $G$ contains an infinite complete subgraph.
\end{thmRR}

Ramsey's Theorem is the following.

\begin{thmR} 
If $G$ is a graph with an infinite number of vertices, then either $G$ contains an infinite complete subgraph or there is an infinite set of vertices of $G$ no two of which are joined by an edge of $G$.
\end{thmR}

Thus Theorem R' is in fact Ramsey's Theorem itself.

\vspace{12pt}

\emph{Added in proof:} Another paper has recently appeared in which Theorem V' is mentioned. It is: John R. Rabung, On applications of van der Waerden's theorem, \emph{Math. Magazine}, 48 (1975) 142--148. Rabung's paper contains, amongst other interesting things, an argument essentially identical with the proof above that Theorem V implies Theorem V'.

\nocite{graham+rothschild1971-2,graham+rothschild1974,hales+jewett1963,khinchin1998,rado1933,rado1943,ramsey1930,vanderwaerden1927,vanderwaerden1971}


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