%%%% 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}