%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-53/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{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{ack}{Acknowledgements}

\title{On Homogeneous Cubes}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{On homogeneous cubes}, Bogazici University J. \textbf{6} (1978),
  13--16.}\bigskip\end{center}

\begin{abstract}
There exists an integer $n \leq 10^{11}$ with the following property. Let the ordinary $n \times n$ square in the plane be divided into $1 \times 1$ ``cells", and let each of these cells be colored either red or blue in any way whatsoever. Then there is a color, say red, an integer $d$, and a $10^4 \times 10^4$ sub-square $S$ of the original square such that every $d \times d$ sub-square of $S$ contains a red cell.

A generalized version of this fact is proved.
\end{abstract}

\section{Notation and Definitions} \label{sec: 1}

If $Y$ is any set, a \emph{k-coloring} of $Y$ is an asignment of one of $k$ different ``colors" to each of the elements of $Y$, That is, a $k$-coloring of $Y$ is a function $c$ from $Y$ to a set of $k$ colors, say $c_1,c_2,\dots,c_k$. A subset $B$ of $Y$ is called \emph{monochromatic} if all the elements of $B$ have been assigned the same color, that is, if for some $i$, $c(x) = c_i$ for all $x$ in $B$. 

The notations $\omega = \{0,1,2,\dots\}$ and $p = \{0,1,\dots,p-1\}$ will be used. As usual, for any set $X$, the symbol $Y^X$ denotes the set of all functions from $X$ to $Y$. If $X$ has only a finite number $t$ of elements, then $\omega^X$ is denoted by $\omega^t$. 

An $N$-cube in $\omega^X$ is any set constructed in the following way. For each element $x$ in $X$, choose an integer $a(x)$. Then the set $\{y \textup{ in } \omega^X: a(x) \leq y(x) \leq a(x) + N\}$ is an $N$-cube. Note that an $N$-cube in $\omega^3$ is an ordinary $N \times N \times N$ cube.

\section{Statement of Results} \label{sec: 2}

\begin{defn} Let a $k$-coloring of $\omega^X$ be given. An $N$-cube $X$ in $\omega^X$ is called \emph{d-homogeneous} is every $(d-1)$-cube contained in $C$ contains an element which has been assigned some one fixed color.
\end{defn}

\begin{thm} \label{thm: 1}
Given a positive integer $k$, a set $X$, and any function $f$ from $\omega$ to $\omega$, there exists an integer $n = n(k,X,f)$ such that if $n^X$ is $k$-colored in any way whatsoever then $n^X$ contains a $d$-homogeneous $f(d)$-cube, for some integer $d$. Furthermore, if $n$ is chosen as small as possible, then $n(1,X,f) = f(1)$ and $n(k,X,f) \leq f(1 + n(k-1,X,f))$ for all $k \geq 2$. (It may be noted that these bounds are independent of $X$.)
\end{thm}

\begin{thm} \label{thm: 2}
Given a positive integer $k$ and a set $X$, let $\omega^X$ be $k$-colored in any way whatsoever. Then there exist $d$ and $d$-homogeneous $N$-cubes for arbitrarily large $N$.
\end{thm}

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

\begin{proof}[Proof of Theorem~\ref{thm: 1}]
Clearly $n(1,X,f)$ exists and equals $f(1)$. Suppose $n(k-1,X,f)$ exists and equals $m$. Suppose now that $n^X$ has been $k$-colored in such a way that every $d$-homogeneous $N$-cube in $n^X$ has $N < f(d)$. Let $D$ be any $M$-cube in $n^X$ which uses only $k-1$ colors. Then by assumption, $M \leq n(k-1,X,f) - 1 = m-1$. Hence every $m$-cube in $n^X$ uses every color, hence $n^X$ itself is an $(m+1)$-homogenous $n$-cube. By assumption, this implies $n < f(m + 1)$, so (having chosen $n$ as large as possible) $n(k,X,f) = n + 1 \leq f(m+1) = f(1 + n(k-1,X,f))$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm: 2}]
Suppose the theorem is false. Then there are an integer $k$, a set $X$, and a particular $k$-coloring of $\omega^X$ such that for every $d$ there is an $f(d)$ such that whenever $C$ is a $d$-homogeneous $N$-cube then $N< f(d)$. That is, there is no $d$-homogeneous $f(d)$ cube, and this contradicts Theorem~\ref{thm: 1}.
\end{proof}

\nocite{brown1969,brown1981}


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