%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-49/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*{remark}{Remark}
\newtheorem*{fact}{Fact}

\title{An Application of Density Ramsey Theory to Transversal Theory}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. Brown, \emph{An application of density Ramsey theory to transversal
  theory}, Bogazici University J. \textbf{10} (1983), 41--46.}\bigskip\end{center}

\begin{abstract}
We apply results of~\cite{brown+buhler1982} and~\cite{brown+buhler1984} to obtain certain sufficient conditions (which involve arbitrarily small ``density") for the existence of a ``k-transversal" of $t$ $s$-block partitions of a set $X$. Along the way, some questions arise of possible independent interest. 
\end{abstract}

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

In this note we prove the two theorems stated below. Section~\ref{sec: 2} contains some necessary preliminaries, Section~\ref{sec: 3} contains the proofs, and Section~\ref{sec: 4} contains some remarks and related questions.

\begin{defn} \label{defn: 1}
Let $X$ be a set, and let $P_1,\dots,P_t$ be $s$-block partitions of $X$. Then $P_1,\dots,P_t$ \emph{separate} the points of $X$ if for every pair of elements $x,y$ of $X$, $x \ne y$, $x$ and $y$ belong to different blocks of at least one of the partitions $P_i$.
\end{defn}

\begin{defn} \label{defn: 2}
If $P = (P(1),\dots,P(s))$ is an (ordered) $s$-block partition of the set $X$, a \emph{transversal} of $P$ is a set $T$ of $s$ elements of $X$, one element from each of the blocks $P(i)$, $1 \leq i \leq s$.
\end{defn}

\begin{defn} \label{defn: 3}
Let $P_1,\dots,P_t$ be $s$-block partitions of a set $X$. a \emph{k-transversal} of $P_1,\dots,P_t$ is an $s$-element subset $T$ of $X$ with the following two properties. 1) For each $i$, $1 \leq i \leq t$, $T$ is either a transversal of $P_i$ or is contained in a single block of $P_i$. 2) For at least $k$ distinct values of $i$, $T$ is a transversal of $P_i$. 
\end{defn}

\begin{defn} \label{defn: 4}
For $s \geq 2$, $\epsilon > 0$, $k \geq 1$, $P(s,\epsilon,k)$ denotes the smallest positive integer (if one exists!) with the following property. If $t \geq P(s,\epsilon,k)$ and $P_1,\dots,P_t$ are $s$-block partitions of a set $X$ which separates the points of $X$, and $|X| \geq \epsilon s^t$, then there exists a $k$-transversal of $P_1,\dots,P_t$.
\end{defn}

\begin{thm} \label{thm: 1} 
$P(2,\epsilon,k)$ and $P(3,\epsilon,k)$ exist for all $\epsilon> 0$ and all $k \geq 1$.
\end{thm}

\begin{thm} \label{thm: 2}
Let $s \geq 2$ be fixed. If $P(s,\epsilon,1)$ exists for all $\epsilon > 0$ then $P(s,\epsilon,k)$ exists for all $\epsilon > 0$ and all $k \geq 1$.
\end{thm}

\section{Preliminaries and further definitions} \label{sec: 2}

Let $s \geq 2$ and $t \geq 1$ be given, let $A = \{1,\dots,s\}$ and let $A^t$ be the $t$-fold cartesian product $A^t = \{a_1\dots a_t: a_i \in A, 1 \leq i \leq t\}$. 

Let $P_1,\dots,P_t$ be $s$-block partitions of a set $X$ which separate the points of $X$. Order the blocks of each partition $P_i$ in an arbitrary way, say 
\[ P_i = (P(i,1),\dots,P(i,s)), \quad 1 \leq i \leq t.\]

Define the mapping $g$ from $X$ into $A^t$ by setting, for each element $x$ of $X$, 
\[g(x) = a_1\cdots a_t, \quad \textup{where $x \in P(1,a_1) \cap \cdots \cap P(t,a_t)$}. \]
Note that $g$ is injective, since $P_1,\dots,P_t$ separate the points of $X$.

\begin{defn} \label{defn: 5}
Let $s \geq 2$, let $A = \{1,\dots,s\}$, and let $k,t$ be positive integers with $t \geq k$. Consider any $s \times t$ matrix $(a_{ij})$, $1 \leq i \leq s$, $1 \leq j \leq t$, which has the property that each column of this matrix is either constant (perhaps different constants for different columns) or is some permutation of the elements of $A$ (perhaps different permutations for different columns), and such that \emph{at least $k$} of the columns are non-constant. Then the $s$ rows of such a matrix, regarded as elements of $A^t$, from a \emph{k-complementary set} in $A^t$.
\end{defn}

(This definition, and the mapping $g$ above, is essentially due to Judith Q. Longyear~\cite{longyear1977}.)

\begin{remark}
Let $P_1,\dots,P_t$ be $s$-block partitions of a set $X$ which separate the points of $X$, and let $Y = g(X)$. It follows from the definition of $g$ that there exists a $k$-transversal of $P_1,\dots,P_t$ if and only if $Y$ contains a $k$-complementary set.
\end{remark}

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

In view of the preceding Remark, $P(s,\epsilon,k)$ (Definition~\ref{defn: 4}) is the smallest positive integer (if one exists) with the following property.

If $A = \{1,\dots,s\}$, $t \geq P(s,\epsilon,k)$, and $Y$ is any subset of $A^t$ with $|Y| > \epsilon s^t$, then $Y$ contains a $k$-complementary set.

To prove Theorem~\ref{thm: 1}, we make use of the following known fact.

\begin{fact} (Corollary to Theorem 1 in~\cite{brown+buhler1984}). The proof of this fact requires the main result given in~\cite{brown+buhler1982}. ) If $F$ is either the $2$-element field or the $3$-element field, and $k \geq 1$, $\epsilon > 0$ are given, there exists an integer $n(|F|,\epsilon,k)$ such that if $t \geq n(|F|,\epsilon,k)$, $V$ is a $t$-dimensional vector space over $F$ and $Y$ is any subset of $V$ with $|Y| > \epsilon |V|$, then $Y$ contains a $k$-dimensional affine subspace (translate of a $k$-dimensional vector subspace) of $V$.
\end{fact}

Note that any $k$-dimensional affine subspace of $V$ contains a $1$-dimensional affine subspace in which there are at least $k$ nonconstant coordinates. (Here we are viewing $V$ as $F^t$.)

Now let $s = 2$ or $s = 3$, let $k \geq 1$, $\epsilon > 0$ be given, let $A = \{1,\dots,s\}$, and let $t \geq n(|A|,\epsilon,k)$. Let $Y$ be any subset of $A^t$ with $Y > \epsilon s^t = \epsilon |A^t|$. Then identifying $A$ with the $s$-element field $F$, and identifying $A^t$ with the $t$-dimensional vector space $V$ over $F$, it follows from the Fact above and the following remark that $Y$ contains a $1$-dimensional affine subspace with at least $k$ non-constant coordinates, that is, $Y$ contains a $k$-complementary set.

This shows that $P(s,\epsilon,k) \leq n(|A|,\epsilon,k)$ (for $s = 2$ or $s = 3$), and completes the proof of Theorem~\ref{thm: 1}.

The proof of Theorem~\ref{thm: 2} is obtained by a slight modification of the proof of Theorem~\ref{thm: 1} in~\cite{brown+buhler1984}. For the sake of completeness we give the modified argument here. 

\begin{lemma} \label{lemma: 1}
Let $s \geq 2$ and $k \geq 1$ be fixed, and assume that $P(s,\epsilon,1)$ exist for all $\epsilon > 0$. Then for each positive integer $r$, the existence of $P(s,1/(r + 1), k)$ implies the existence of $P(s,1/r, k + 1)$.
\end{lemma}

\begin{proof}
Let $A = \{1,\dots,s\}$, let $no = P(s,1/(r + 1), k)$, and let $e$ be the number of distinct $k$-complementary sets in $A^{no}$. Let $\epsilon' = 1/(er^2)$, and let $n\iota = P(s,\epsilon', 1)$. We now claim that $P(s,1/r,k + 1) \leq no + n\iota$.

To see this, let $Y$ be any subset of $A^{no + n\iota}$ with $|Y| > 1/r \cdot s^{no + n\iota}$. We need to show that $Y$ contains a $(k + 1)$-complementary set. 

For each $z \in A^{n \iota}$, let $W_z$ denote the set $A^{no} \times \{z\}$. Then 
\[ A^{no + n\iota} = \cup \{W_z: z \in A^{n\iota}\}. \]

Note that if $|Y \cap W_z| > 1/(r + 1) \cdot s^{no}$, then by the definition of $no$, $Y$ must contain a $k$-complementary set. 

Let $u$ denote the number of elements $z$ in $A^{n\iota}$ such that $|Y \cap W_z| \leq 1/(r + 1) \cdot s^{no}$.

Then we have 
\[ 1/r \cdot s^{no + n\iota} < |Y| = \sum |Y \cap W_z| \leq u/(r + 1) \cdot s^{no} + (s^{n\iota} - u)\cdot s^{no}, \]
hence $u(1 - 1/(r + 1)) < s^{n\iota}(1 - 1/r)$, $u < s^{n\iota}(1 - 1/r^2)$, $s^{n\iota}/r^2 < s^{n\iota} - u$.

Therefore there are 
\[ d = s^{n\iota} - u > s^{n\iota}/r^2 \]
elements $z$ in $A^{n\iota}$ such that 
\[ |Y \cap W_z| > 1/(r + 1)\cdot s^{n \iota}, \]
and each of these sets $Y \cap W_z$ contains a $k$-complementary set 
\[ U_z \times \{z\}, \]
where $U_z$ is a $k$-complementary set contained in $A^{no}$.

Since there are only $e$ distinct $k$-complementary sets in $A^{no}$, at least $d/e$ of the sets $U_z \times \{z\}$ must have the form $U \times \{z\}$ for a fixed $k$-complementary set $U$ in $A^{no}$. Let these be 
\[ U \times \{z_1\}, \dots, U \times \{z_h\}, \]
where $h \geq d/e$.

Let $Y' = \{z_1,\dots,z_h\}$. Then $Y'$ is a subset of $A^{n\iota}$ with 
\[ |Y'| = h \geq d/e > s^{n \iota}/(er^2) = \epsilon' \cdot s^{n\iota}. \]
Therefore $Y'$ contains a $1$-complementary set. Re-numbering if necessary, let this $1$-complementary set be $z_1,\dots,z_s$.

We now have that $Y$ contains $U \times \{z_1\}, \dots, U \times \{z_s\}$, where $U$ is a $k$-complementary set in $A^{no}$ and $\{z_1,\dots,z_s\}$ is a $1$-complementary set in $A^{n\iota}$. If $U = \{w_1,\dots,w_s\}$, then $Y$ contains the $(k + 1)$-complementary set 
\[ w_1 \times z_1, \dots, w_s \times z_s. \]

This completes the proof of the Lemma.
\end{proof}

Theorem~\ref{thm: 2} now follows from the Lemma by induction on $k$. Indeed, the hypothesis of Theorem~\ref{thm: 2} is the case $k = 1$. For the induction step, if $P(s,\epsilon,k)$ exists for all $\epsilon > 0$ then it exists for all $\epsilon = 1/(r + 1)$, $r \geq 1$, hence by the Lemma $P(s,1/r,k + 1)$ exists for all $r \geq 1$, hence $P(s,\epsilon,k+1)$ exists for all $\epsilon > 0$. 

\section{Remarks and questions} \label{sec: 4}

A \emph{combinatorial line} $T$ in $A^t$ (where $A = \{1,\dots,s\}$) is a $1$-complementary set of a very special type. When the $t$-tuples of $T$ are regarded as the rows of an $s \times t$ matrix, then each column of this matrix is either constant or is a \emph{single fixed} permutation of the elements of $A$.

The celebrated Hales-Jewett theorem~\cite{hales+jewett1963} states that if $s,r$ are given there exists a smallest positive integer $HJ(s,r)$ such that if $A = \{1,\dots,s\}$,$ t \geq HJ(s,r)$, and $A^t$ is $r$-colored (that is, a mapping $c: A^t \mapsto \{1,\dots,r\}$ is given) then there exists a combinatorial line $T$ in $A^t$ which is monochromatic (that is, the mapping $c$ restricted to $T$ is constant.)

The only known upper bounds for the function $HJ(s,r)$ are extremely large, to say the least. (See~\cite{deuber+voigt1983,graham1979,graham+rothschild1971-2,graham+rothschild+spencer1980} for elegant proofs, generalizations and applications of the Hales-Jewett theorem, and for further discussion of these bounds. See also the numerous references in the excellent survey article~\cite{deuber+voigt1983}.)

Let $f(s,r)$ denote the smallest positive integer such that if $A = \{1,\dots,s\}$, $t \geq f(s,r)$, and $A^t$ is $r$-colored then there exists a $1$-complementary set in $A^t$ which is monochromatic. Perhaps a ``reasonable" (primitive recursive?!) upper bound can found for the function $f(r,s)$.

One could also ask for bounds on the function $f(s,r,k)$, the smallest positive integer such that if $A = \{1,\dots,s\}$, $t \geq f(s,r,k)$, and $A^t$ is $r$-colored, there exists a $k$-complementary set in $A^t$ which is monochromatic. 


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