%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-45/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{thm}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem*{remark}{Remarks}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}


\title{A Graph-Theoretic Conjecture Which Implies Szemer\'edi's Theorem}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, \emph{A graph-theoretic conjecture which implies Szemer\'edi's
  theorem}, Bull. Istanbul Tech. Univ. \textbf{37} (1984), 59--63.}\bigskip\end{center}

\begin{abstract} We briefly review the history of Szemer\'{e}di's theorem, and its equivalence to Furstenberg's theorem on multiple recurrence of measure-preserving transformations. We then show that the truth of a certain graph-theoretic conjecture would imply Szemer\'{e}di's theorem.
\end{abstract} 

\section{Introduction} \label{sec: 1}

In 1927, B. L. van der Waerden~\cite{vanderwaerden1927} published a proof of the following theorem, opening an area of research which continues to grow at an explosive rate.

\begin{thm} \label{thm: 1}
For every pair $k,r$ of positive integers there exists an integer $n = n(k,r)$ such that if the set $[1,n] = \{1,2,\dots,n\}$ is partitioned in any way into $r$ subsets $A_1,A_2,\dots,A_r$, then at least one of the subsets $A_i$ must contain a $k$-term arithmetic progression $a, a + d, a + 2d,\dots, a + (k-1)d$.
\end{thm}

(See~\cite{deuber+voigt1983} for an up-to-date survey of results and current questions of interest in this area, including an extensive list of references.)

In 1975, E. Szemer\'{e}di~\cite{szemeredi1975} proved the following profound generalization of this result, which had been conjectured in 1936 by Erd\H{o}s and Tur\'{a}n~\cite{erdos+turan1936}.

\begin{thm} \label{thm: 2}
Let $k$ be an arbitrary positive integer, and let $\varepsilon$ be an arbitrary positive real number. Then there exists an integer $n_0 = n_0(k,\varepsilon)$ such that if $n \geq n_0$ and $A$ is any subset of $[1,n]$ which contains more than $\varepsilon n$ elements, then $A$ contains a $k$-term arithmetic progression.
\end{thm}

Earlier partial results were obtained by K. F. Roth in 1953~\cite{roth1953}, who proved the result for the special case $k = 3$, by E. Szemer\'{e}di in 1969~\cite{szemeredi1969}, who settled the question for the special case $k = 4$, and by Felix Behrend in 1938~\cite{behrend1938}, who proved an interesting consequence of the falsity of Theorem~\ref{thm: 2}.

In 1976 H. Furstenberg observed that Theorem~\ref{thm: 2} is equivalent to the following ``multiple recurrence" theorem.

\begin{thm} \label{thm: 3}
Let $(X,\mathcal{B}, \mu)$ be a probability measure space. Let $T$ be an invertible, measure-preserving transformation on $(X, \mathcal{B}, \mu )$, and let $A \in \mathcal{B}$ be any set of positive measure. Then for every positive integer $k$ there exists a subset $B$ of $A$ with $\mu(B) > 0$ and a positive integer $n$ such that 
\[ T^n(B) \cup T^{2n}(B) \cup \cdots \cup T^{(k-1)n}(B) \subset A. \]
\end{thm} 

Furstenberg found an ergodic theoretical proof of Theorem~\ref{thm: 3}~\cite{furstenberg1977}, thus giving a new proof of Szemer\'{e}di's Theorem. (A somewhat simplified exposition of this proof is given by Furstenberg, Kaznelso, and Ornstein in~\cite{furstenberg+katznelson+ornstein1982}).

\section{A graph-theoretic conjecture which implies Szemer\'{e}di's theorem}

\begin{conj} Let $t,k$ be arbitrary positive integers. Then there exists a positive integer $N = N(t,k)$ with the following property. Let $n \geq N$, and let the edges of the complete graph on $n + 1$ vertices, $K_{n + 1}$, be colred with $tn$ colors, in such a way that no two adjacent edges have been assigned the same color. Then there exists either a bichromatic circuit (a circuit whose edges are colored alternately using only two colors) or a bichromatic path of length $k$ (a path with $k$ edges, which are colored alternately using only two colors).
\end{conj}

\begin{proof}[Proof that the conjecture implies Szemer\'{e}di's theorem]
Suppose that Szemer\'{e}di's theorem is false. Then for some fixed positive integers $s$ and $k$, and arbitrarily large integers $n$, there exist sets $A_n$ such that $A_n \subset [1,sn]$, $|A_n| = n + 1$, and $A_n$ contains no $k$-term arithmetic progression.

(We will use these sets $A_n$ to show that $N(2s, 2k - 1)$ does not exist, contradicting the conjecture).

It follows that $A_n$ contains no $k$-term arithmetic progression \emph{modulo} $2sn + 1$, that is, $A_n$ does not contain $a_1,a_3,\dots,a_k$ (not necessarily distinct) such that $a_1 \not\equiv a_2$ (mod $2sn + 1$) and 
\[ a_2 - a_1 \equiv a_3 - a_2\equiv \cdots \equiv a_k - a_{k -1} \quad (\textup{mod }2sn + 1). \]
Now let $K(A_n)$ denote the complete graph with vertex set $A_n$. We color the edges of $K(A_n)$, using the $2sn$ elements of $[1,2sn]$ as colors, in the following way. For $x,z$ in $K(A_n)$, $x \ne z$, we assign to the edge $\{x,z\}$ the unique element $y$ in $[1,2sn]$ such that 
\[ x + z \equiv 2y \quad (\textup{mod }2sn + 1). \]
Note that this just means that $x,y,z$ form a $3$-term arithmetic progression modulo $2sn + 1$.

We can now show that there does not exist any bichromatic path of length $2k - 1$.

Suppose on the contrary that $a_1b_1a_2b_2\cdots a_{k-1}b_{k-1}a_k$ are the vertices (in $K(A_n)$) of a bichromatic path of length $2k - 1$. Then the edges $\{a_1,b_1\}, \{a_2,b_2\}, \dots, \{a_{k -1}, b_{k-1}\}$ all have say color $y$, so that 
\[ 2y \equiv a_1 + b_1 \equiv a_2 + b_2 \equiv \cdots \equiv a_{k-1} + b_{k-1} \quad (\textup{mod }2sn + 1). \]
Similarly,
\[ b_1 + a_2 \equiv b_2 + a_3 \equiv \cdots \equiv b_{k-1} + a_k \quad (\textup{mod }2sn + 1). \]
In particular, $a_i + b_i \equiv a_{i + 1} + b_{i+1}$ (mod $2sn + 1$) and $b_{i + 1} + a_{i + 2} \equiv b_i + a_{i + 1}$ (mod $2sn + 1$). Adding these two congruences gives
\[ a_i + a_{i + 2} \equiv 2a_{i + 1} \quad (\textup{mod }2sn + 1), \quad 1 \leq i \leq k - 2. \]
Hence $a_1,a_2,\dots,a_k$ form a $k$-term arithmetic progression modulo $2sn + 1$ which is contained in $A_n$, contradicting one of our assumptions about $A_n$.

Therefore no bichromatic path of length $2k - 1$ exists, for this particular coloring of the edges of $K(A_n)$.

Similarly, no bichromatic circuit can exist, we just go around the circuit (which must have even length) enough times to obtain a $k$-term arithmetic progression modulo $2sn + 1$.

Since these coloring exist for arbitrarily large $n$, we conclude that $N(2s,2k - 1)$ does not exist. Thus the falsity of Szemer\'{e}di's theorem implies the falsity of the conjecture.
\end{proof}

\section{Remarks} \label{sec: 3}

When $t = 1$, we can take $N(1,k) = 3$. Indeed, if $n \geq 3$ is even then no coloring of $K_{n + 1}$ with $n$ colors, where no two adjacent edges have the same color, is possible. If $n \geq 3$ is odd and the edges of $K_{n + 1}$ are colored with $n$ colors, where no two adjacent edges have the same color, then for each color, exactly $(n + 1)/2$ edges must have the same color. Hence for any two distinct colors, the set of edges having these two colors will be the union of bichromatic circuits.

(These bichromatic circuits can be small. If $n + 1 = 2^m$, we can label the vertices of $K_{n + 1}$ with the $n + 1$ elements of the $(n + 1)$-element field, and then use the $n$ non-zero elements of this field as colors by assigning the color $a + b$ to the edge $\{a,b\}$, for each pair $a,b, a \ne b$ of vertices. Under this coloring, every bichromatic circuit is a $4$-circuit).

If we use $n + 1$ colors for the edges of $K_{n + 1}$, instead of $n$ colors, there need not exist any bichromatic circuits at all. Indeed, let $n + 1 = p$, where $p$ is an odd prime. Label the vertices of $K_{n + 1}$ with the elemtns of the $(n + 1)$-element field, and again assign to the edge $\{a,b\}$ the color $a + b$, for each pair $a,b, a \ne b$, of vertices. Now the zero element of the field is used as a color, and there are no bichromatic circuits. In fact, given any two colors, the set of all edges in these two colors is a path of length $p - 1$. (This example is due to Joel Spencer~\cite{spencerPC}).

At present we are unable to settle the conjecture even for the special case $t = 2$. (Note that the conjecture makes sense even if we take $t$ to be, for example, $3/2$). 


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