%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-40/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}{Remark}
\newtheorem*{app}{Applications}
\newtheorem*{conj}{Conjecture}


\title{Affine and Combinatorial Binary $m$-Spaces}
\author{T. C. Brown}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown}, \emph{Affine and combinatorial binary $m$-spaces}, J. Combin. Theory
  Ser. A \textbf{38} (1985), 25--34.}\bigskip\end{center}

\begin{abstract} Let $V(n)$ denote the $n$-dimensional vector space over the 2-element field. Let $a(m,r)$ (respectively, $c(m,r)$) denote the smallest positive integer such that if $n \geq a(m,r)$ (respectively $n \geq c(m,r)$), and $V(n)$ is arbitrarily partitioned into $r$ classes $C_i$, $1 \leq i \leq r$, then some class $C_i$ must contain an $m$-dimensional affine (respectively, combinatorial) subspace of $V(n)$. Upper bounds for the functions $a(m,r)$ and $c(m,r)$ are investigated, as are upper bounds for the corresponding ``density functions" $\bar{a}(m,\varepsilon)$ and $\bar{c}(m,\varepsilon)$.
\end{abstract}

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

Throughout, $V(n)$ denotes the $n$-dimensional vector space over the 2-element field $\mathbb{F}_2 = \{0,1\}$:
\[ V(n) = \{(x_1,\dots,x_n): x_i \in \mathbb{F}_2, 1 \leq i \leq n\}. \]
For integers $m \geq 1$, $r \geq 1$, $a(m,r)$ is defined to be the smallest positive integer such that if $n \geq a(m,r)$ and $V(n)$ is arbitrarily partitioned into $r$ classes $C_i$, $ 1 \leq i \leq r$, then some class $C_i$ contains an affine $m$-space. (An \emph{affine $m$-space} is any translate (coset) of an $m$-dimensional vector subspace of $V(n)$. An affine 1-space is usually called an \emph{affine line}.)

Similarly, $c(m,r)$ is defined to be the smallest positive integer such that if $n \geq c(m,r)$ and $V(n)$ is arbitrarily partitioned into $r$ classes then some class must contain a combinatorial $m$-space. (The definition of combinatorial $m$-space is given in Section~\ref{sec: 3} below.)

The existence of $a(m,r)$ and $c(m,r)$ for all $m,r$ is a consequence of a special case of the extended Hales-Jewett theorem~\cite{graham+rothschild+spencer1980,hales+jewett1963}.

In this note we investigate upper bounds for the functions $a(m,r)$ and $c(m,r)$.

We also inverstigate upper bounds for the corresponding density functions $\bar{a}(m,\varepsilon)$ and $\bar{c}(m,\varepsilon)$, which are defined as follows.

For any integer $m \geq 1$ and real number $\varepsilon > 0$, $\bar{a}(m,\varepsilon)$ (respectively, $\bar{c}(m,\varepsilon)$) is defined to be the smallest integer such that if $n \geq \bar{a}(m,\varepsilon)$ (respectively, $n \geq \bar{c}(m,\varepsilon)$) and $A$ is an arbitrary subset of $V(n)$ which contains at least $\varepsilon |V(n)|$ elements, then $A$ must contain an affine (respectively, combinatorial) $m$-space.

The existence of $\bar{a}(m,\varepsilon)$ follows from a result of Brown and Buhler~\cite[Lemma\ 1]{brown+buhler1982}, which in turn is based upon a lemma of Szemer\'{e}di~\cite{szemeredi1975}. (See also Graham, Rothschild, and Spencer~\cite[p.\ 44]{graham+rothschild+spencer1980} and Graham~\cite[p.\ 19]{graham1981}.)

The existence of $\bar{c}(m,\varepsilon)$ is a consequence of a different result of Brown and Buhler~\cite{brown+buhler1984}. (The existence of $\bar{a}(m,\varepsilon)$ also folows from this latter result.)

\section{Upper bounds for $a(m,r)$ and $\bar{a}(m,\varepsilon)$} \label{sec: 2}

For the definitions of $a(m,r)$ and $\bar{a}(m,\varepsilon)$, see Section~\ref{sec: 1}.

\begin{thm} \label{thm: 1}
For $m \geq 1$, $k \geq 1$, 
\begin{equation} \bar{a}(m,2^{-k}) \leq 2^m (k + 2). \label{eq: 1} \end{equation} 
\end{thm}

\begin{proof} Let $m \geq 1$, $k \geq 1$ be given, and let $n = 2^m(k + 2)$.

Let $V = V(n)$, so that $|V| = 2^n$ and $n = \log |V|$. (All logarithms here are taken with base 2.)

Now let $\varepsilon = 2^{-k}$, and let 
\[ A \subset V, \quad |A| \geq \varepsilon |V|. \]
One obtains, after a little juggling,
\[ m = \log \log |V| - \log \log (4/\varepsilon). \]
It is shown in~\cite{brown+buhler1982} that under exactly these circumstances the subset $A$ must contain an affine $m$-space. Therefore $\bar{a}(m,2^{-k}) \leq n = 2^m(k +2)$, as required.
\end{proof}

\begin{remark} \label{rem: 1}
When $\varepsilon$ is not $2^{-k}$, one can still use Theorem~\ref{thm: 1} to get 
\[ \bar{a}(m,\varepsilon) \leq \bar{a}(m,2^{-k}) \leq 2^m(k + 2), \]
where
\[ 2^{-k} < \varepsilon < 2^{-(k - 1)}. \]
\end{remark}

\begin{thm} \label{thm: 2}
For $m \geq 1, k \geq 1$, 
\begin{equation} a(m,2^k) \leq 2^m(k + 2). \label{eq: 2} \end{equation} 
\end{thm}

\begin{proof} This follows immediately from Theorem~\ref{thm: 1}, since if $V(n)$ is partitioned into $2^k$ classes, then at least one of these classes has density at least $2^{-k}$. That is, if 
\[ V(n) = C_1 \cup \cdots \cup C_{2^k}, \]
then for some $i$,
\[ |C_i| \geq 2^{-k} |V(n)|. \]
Hence $a(m,2^k) \leq \bar{a}(m,2^{-k}) \leq 2^m (k + 2)$.
\end{proof}

\begin{remark} \label{rem: 2}
If $r$ is not $2^k$, then one obtains
\[ a(m,r) \leq a(m,2^k) \leq 2^m(k + 2) \]
where 
\[ 2^{k - 1} < r < 2^k. \]
\end{remark}

\begin{thm} \label{thm: 3}
\begin{align} a(m,1) &= m, &&m \geq 1, \label{eq: 3} \\
a(1,r) &= 1 + [\log_2 r], &&r \geq 1, \label{eq: 4} \\
a(2,2^k -1) &\leq 3k, &&k \geq 2, \label{eq: 5} \\
a(3,2^k - 1) &\leq 10k - 2, &&k \geq 3, \label{eq: 6} \\
a(3,3) &\leq 15, &&a(4,3) \leq 55. \label{eq: 7} 
\end{align}
\end{thm}

\begin{proof} Equalities~(\ref{eq: 3}) and~(\ref{eq: 4}) are obvious. Note that any 2-element suset of $V(n)$ is an affine line in $V(n)$.

Inequalities~(\ref{eq: 5}) and~(\ref{eq: 6}) are proved using the following method.

To prove~(\ref{eq: 5}), fix $k \geq 2$ and let 
\[ V(3k) = V(2k) \times V(k) \]
be partitioned into $2^k - 1$ classes $C_i$, $1 \leq i \leq 2^k - 1$. We need to show that some affine 2-space in $V(3k)$ is contained in some $C_i$. 

Let $y \in V(2k)$. Then $\{y\} \times V(k)$ is partitioned into $2^k - 1$ classes
\[ (\{y\} \times V(k)) \cap C_i, \quad 1 \leq i \leq 2^k - 1. \]
Since $a(1,2^k - 1) = k$, there is an affine line
\[ f(y) \subset V(k) \]
such that the affine line
\[ \{y\} \times f(y) \subset V(3k) \]
is contained in some $C_i$.

Now we partition $V(2k)$ into $(2^k - 1)^2$ classes $D(i,j)$, $1 \leq i \leq 2^k - 1$, $1 \leq j \leq 2^k - 1$, in the following way. Let the distinct 1-dimensional vector subspaces of $V(k)$ be denoted by $S_j$, $1 \leq j \leq 2^k - 1$. Then the element $y$ of $V(2k)$ belongs to the class $D(i,j)$ if and only if $\{y \} \times f(y) \subset C_i$ and $f(y)$ is a translate of $S_j$.

Since $a(1,(2^k - 1)^2) = 1 + [\log_2(2^k - 1)^2] = 2k$, there is an affine line $\{y_1,y_2\}$ contained in some $D(i,j)$. It follows that
\[ \{y_1\} \times f(y_1) \cup \{y_2\} \times f(y_2) \]
is an affine 2-space contained in $C_i$. This proves~(\ref{eq: 5}).

The proof of~(\ref{eq: 6}) uses the same idea. Fix $k \geq 3$, and let
\[ V(10k - 2) = V(7k - 2) \times V(3k) \]
be partitioned into $2^k - 1$ classes $C_i$, $ 1\leq i \leq 2^k - 1$. We need to show that some affine 3-space of $V(10k - 2)$ is contained in some $C_i$.

Let $y \in V(7k - 2)$; then $\{y \} \times V(3k)$ is partitioned into 
\[ (\{y\} \times V(3k)) \cap C_i, \quad 1 \leq i \leq 2^k - 1. \]
Since $a(2,2^k - 1) \leq 3k$, there is an affine 2-space
\[ f(y) \subset V(3k) \]
such that the affine 2-space
\[ \{y \} \times f(y) \subset V(10k - 2) \]
is contained in some $C_i$.

Now we partition $V(7k - 2)$ into $(2^k - 1)t$ classes $D(i,j)$, $1 \leq i \leq 2^k - 1$, $1 \leq j \leq t$, where 
\[ t = \frac{(2^{3k} - 1)(2^{3k} - 2)}{(2^2 - 1)(2^2 - 2)} \]
is the number of 2-dimensional vector subspaces of $V(3k)$, just as before: Let the 2-dimensional vector subspaces of $V(3k)$ be denoted by $S_j$, $1 \leq j\leq t$. Then the element $y$ of $V(7k - 2)$ belongs to the class $D(i,j)$ if and only if $\{y\} \times f(y) \subset C_i$ and $f(y)$ is a translate of $S_j$.

Now $a(1,(2^k - 1)t) = 1 + [\log_2(2^k - 1)t] = 7k - 2$ (for this we need $k \geq 3$), and hence there is an affine line $\{y_1,y_2\}$ contained in some $D(i,j)$. It follows that 
\[ \{y_1\} \times f(y_1) \cup \{y_2\} \times f(y_2) \]
is an affine 3-space contained in $C_i$. This proves~(\ref{eq: 6}).

The bounds in~(\ref{eq: 7}) are proved using the same method.
\end{proof}

\begin{remark} \label{rem: 3}
If the method above is continued to $a(4,2^k - 1)$, $a(5,2^k - 1)$ and so on, the resulting bounds are not as strong as those given by Theorem~\ref{thm: 2} (With the exception of $a(4,3)$.)
\end{remark}

\section{Upper bounds for $c(m,r)$ and $\bar{c}(m,\varepsilon)$} \label{sec: 3}

For the definitions of $c(m,r)$ and $\bar{c}(m,\varepsilon)$, see Section~\ref{sec: 1}.

\begin{defn} A \emph{combinatorial $m$-space} in $V(n)$ is any set $S$ (of $2^m$ elements of $V(n)$) which can be described as follows. For some partition
\[ \{ 1,2,\dots,n\} = B_0 \cup B_1 \cup \cdots \cup B_m, \]
where $B_0$ may be empty but $B_j$ is not empty, $1 \leq j \leq m$, and for some function $f$ from $B_0$ into $\mathbb{F}_2$, $S$ is the set of all points $(x_1,\dots,x_n)$ in $V(n)$ such that 
\[ x_i = f(i), \quad \textup{for }i \in B_0, \]
\[ x_i = x_{i'}, \quad \textup{for }i,i' \in B_j, 1 \leq j \leq m. \]
\end{defn}

A combinatorial 1-space is usually called a \emph{combinatorial line}.

For example, with $m = 3$, $n = 8$, $B_0 = \{1,2\}$, $B_1 = \{3,4\}$, $B_2 = \{5\}$, $B_3 = \{6,7,8\}$, $f(1) = f(2) = 1$, $S$ is the 3-space
\[ \begin{matrix} &11 &00 &0 &000 \\ &11 &00 &0 &111 \\ &11 &00 &1 &000 \\ &11 &00 &1 &111 \end{matrix} \qquad 
\begin{matrix} &11 &11 &0 &000 \\ &11 &11 &0 &111 \\ &11 &11 &1 &000 \\ &11 &11 &1 &111 \end{matrix}. \]
With $m = 1$, $n = 8$, $B_0 = \{1,2,3,4\}$, $B_1 = \{5,6,7,8\}$, $f(1) = f(4) = 1$, $f(2) = f(3) = 0$, $S$ is the line
\[ \begin{matrix} 10010000 \\ 10011111 \end{matrix}. \]

\begin{thm} \label{thm: 4} 
For each $r \geq 1$, 
\[ c(1,r) = r. \]
\end{thm} 

\begin{proof} If $V(r) = C_1 \cup \cdots \cup C_r$, then some two of 
\begin{align*} 
&000 \cdots 0 \\
&100 \cdots 0 \\
&\vdots \; \vdots \; \vdots \quad \: \; \: \vdots \\
&111 \cdots 1 
\end{align*}
belong to the same class $B_i$. Hence $c(1,r) \leq r$.

Let $V(r - 1) = C_0 \cup \cdots \cup C_{r - 1}$, where for $0 \leq i \leq r - 1$,
\[ C_i = \left\{ (x_1,\dots,x_{r - 1}) \in V(r - 1): \sum_{j=1}^{r - 1} x_j = i \right\}. \]
Then no $C_i$ contains a combinatorial line, Hence $c(1,r) \geq r$.
\end{proof}

The proof of Theorem~\ref{thm: 5} below is similar to the proof of Theorem~\ref{thm: 3}. The main part of the proof is contained in the following Lemma.

\begin{lemma} \label{lemma: 1} 
Let $m \geq 1$, $r \geq 1$, be given, and let $t(m,r)$ be the number of distinct combinatorial $m$-spaces contained in $V(c(m,r))$. Then 
\[ c(m + 1, r) \leq r \cdot t(m,r) + c(m,r). \]
\end{lemma}

\begin{proof} 
For convenience write $t = t(m,r)$ and $s = c(m,r)$. Let 
\[ V(rt + s) = V(rt) \times V(s) \]
be partitioned into $r$ classes $C_i$, $1 \leq i \leq r$. To show that some combinatorial $(m + 1)$-space in $V(rt + s)$ is contained in some $C_i$, we proceed just as in the proof of Theorem~\ref{thm: 3}.

For each $y \in V(rt)$, $\{y\} \times V(s)$ has been partitioned into classes
\[ \{y \} \times V(s) \cap C_i, \quad 1 \leq i \leq r, \]
and since $s = c(m,r)$ there is a combinatorial $m$-space
\[ f(y) \subset V(s) \]
such that the combinatorial $m$-space
\[ \{y\} \cap f(y) \subset V(rt + s) \]
is contained in some $C_i$. 

Now partition $V(rt)$ into $rt$ classes $D(i,j)$, $1 \leq i \leq r$, $1 \leq j \leq t$, by putting the element $y$ of $V(rt)$ into the class $D(i,j)$ if and only if $\{y\} \times f(y) \subset C_i$ and $f(y) = S_j$, where $S_1,\dots,S_t$ are the combinatorial $m$-spaces in $V(s)$.

Since $c(1,rt) = rt$, there is a combinatorial line $\{y_1,y_2\}$ contained in some $D(i,j)$, and therefore
\[ \{y_1\} \times f(y_1) \cup \{y_2\} \times f(y_2) \]
is a combinatorial $(m + 1)$-space contained in $C_i$.
\end{proof}

\begin{lemma} \label{lemma: 2}
The number of combinatorial $m$-spaces in $V(s)$ is 
\[ \frac{1}{m!} \sum_{j=0}^m (-1)^j \binom{m}{j} ( m + 2 - j)^s. \]
\end{lemma}

\begin{proof} Each combinatorial $m$-space in $V(s)$ corresponds to an $s$-tuple on the $m + 2$ symbols $0,1,b_1,\dots,b_m$, in which each $b_j$, $1 \leq j\leq m$, occurs at least once. In the examples described after the Definition above, the 3-space corresponds to $11b_1b_1b_2b_3b_3b_3$, and the 1-space (line) corresponds to $1001b_1b_1b_1b_1$. Counting by inclusion-exclusion gives the result.
\end{proof}

\begin{thm} \label{thm: 5}
For $m = 2$, $r \geq 1$, we have 
\[ c(2,r) < r \cdot (3^r - 2^r) + r < r \cdot 3^r. \]
In general, for $m \geq 2$, $r \geq 1$,
\[ c(m,r) < r \cdot ((m + 1)r)^{(m^r)^{\cdot^{\cdot^{(4^r)^{(3^r)}}}}}. \]
\end{thm}

\begin{proof}
This is a crude estimate based on Lemmas~\ref{lemma: 1} and~\ref{lemma: 2}. 
\end{proof}

We now turn to upper bounds for the function $\bar{c}(m,\varepsilon)$.

\begin{thm} \label{thm: 6}
For $m \geq 1$, $r \geq 1$, 
\begin{align*} \bar{c}(m,1) &= 1; \\
\bar{c}(1,1/r) &\leq r^2.
\end{align*}
\end{thm}

\begin{proof} It is an easy consequence of Sperner's lemma on families of pairwise incomparable subsets of a set (see~\cite{graham1981} for details) that if $A$ is any subset of $V(n)$ such that $A$ contains no combinatorial line then 
\[ |A| \leq \binom{n}{[n/2]}. \]
Using 
\[ n^ne^{-n} \sqrt{2\pi n} e^{1/(12n + 1)} \leq n! \leq n^ne^{-n} \sqrt{2\pi n} e^{1/12n}, \]
one obtains
\[ \binom{n}{[n/2]} < \sqrt{\frac{2}{\pi}} \cdot \frac{1}{\sqrt{n}} \cdot 2^n, \quad n \geq 1. \]
Hence if $A \subset V(r^2)$, $|A| \geq (1/r)|V(r^2)|$, then 
\[ |A| \geq \frac{1}{r} \cdot 2^{r^2} > \sqrt{\frac{2}{\pi}} \cdot \frac{1}{\sqrt{r^2}} \cdot 2^{r^2} > \binom{r^2}{[r^2/2]}, \]
and therefore $A$ contains a combinatorial line.
\end{proof}

\begin{lemma} \label{lemma: 3}
For $m \geq 1$, $r \geq 1$, let $n = \bar{c}(m,1/(r + 1))$ and let $e$ be the number of distinct combinatorial $m$-spaces contained in $V(n)$. Then 
\[ \bar{c}(m + 1, 1/r) \leq n + r^4e^2. \]
In particular, using Theorem~\ref{thm: 6} and Lemma~\ref{lemma: 2}, 
\[ \bar{c}(2,1/r) \leq (r + 1)^2 + r^4(3^{(r + 1)^2} - 2^{(r + 1)^2})^2. \]
\end{lemma}

\begin{proof} It is shown in~\cite{brown+buhler1984} that 
\[ \bar{c}(m + 1, 1/r) \leq n + \bar{c}(1,(r^2e)^{-1}). \]
Applying Theorem~\ref{thm: 6} gives the result.
\end{proof}

One can now apply Lemma~\ref{lemma: 3} (and Lemma~\ref{lemma: 2}) repeatedly to get an explicit upper bound for $\bar{c}(m,1/r)$. One estimate obtained in this way is the following.

\begin{thm} \label{thm: 7}
For $m \geq 2$, $r \geq 1$, let $s = (r +m - 1)^4$. Then 
\[ c(m,1/r) \leq r^4((m + 1)^s)^{(m^s)^{\cdot^{\cdot^{(4^s)^{(3^s)}}}}}. \]
\end{thm}

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

Since Theorem~\ref{thm: 1} above is surely \emph{much} stronger than Theorem~\ref{thm: 2}, it should be possible to considerably strengthen Theorem~\ref{thm: 2}.

Replacing the two-element field $\mathbb{F}_2$ by the three-element field $\mathbb{F}_3$ (or any larger field) leads to considerable difficulties. Let $a(m,r,q), \dots$ be the functions defined analogously to $a(m,r), \dots$, where $\mathbb{F}_2$ is replaced by the $q$-element field $\mathbb{F}_q$. (The definitions of affine $m$-space and combinatorial $m$-space remain unchanged. Note, however, that the definition of a combinatorial $m$-space does not require a finite field, but only a finite set.)

The existence of $a(m,r,q)$ and $c(m,r,q)$ follows from the Hales-Jewett theorem. The existence of $\bar{a}(m,\varepsilon,q)$ is known only for $q = 2$ and $q = 3$~\cite{brown+buhler1982,brown+buhler1984}, and the existence of $\bar{c}(m,\varepsilon, q)$ is not known even for $q = 3$. R. L. Graham has offered a reward~\cite{graham1981} for an answer to the question of the existence of $\bar{c}(1,\varepsilon,3)$.

Following the methods used above to prove Theorems~\ref{thm: 3},~\ref{thm: 5}, and~\ref{thm: 7}, one could calculate upper bounds for, say, $a(m,r,3)$ and $\bar{a}(m,\varepsilon,3)$, and $c(m,r,3)$ in terms of upper bounds for the case $m = 1$. However, no satisfactory upper bounds for $a(1,r,3)$, $\bar{a}(1,\varepsilon,3)$, and $c(1,r,3)$ have been found.

(It is trivial that $a(1,1,3) = 1$ and $a(1,2,3) = 2$. A recent calculation~\cite{brown1985-2} shows that $a(1,3,3) = 4.$)

Finally, we remark that by identifying $V(n)$ with the set of subsets of $\{1,\dots,n\}$ in the natural way, the combinatorial $m$-spaces in $V(n)$ become identified with collections of the form 
\[ \left\{ A_0 \cup \bigcup_{i \in I} A_i: I \subset \{1,\dots,n\} \right\}, \]
where $A_0, A_1,\dots,A_m$ are pairwise disjoint subsets of $\{1,\dots,n\}$ and $A_1,\dots,A_m$ are non-empty.

The functions $c(m,r)$ and $\bar{c}(m,1/r)$ can be interpreted from this point of view. Related bounds have been found by Alan Taylor~\cite{taylor1981} for the case where $A_0$ is empty and $I$ is non-empty.


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