Title: A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem,
Abstract: For integers $n$ and $k$, the density Hales-Jewett number $c_{n,k}$ is
defined as the maximal size of a subset of $[k]^n$ that contains no
combinatorial line. We show that for $k \ge 3$ the density Hales-Jewett number
$c_{n,k}$ is equal to the maximal size of a cylinder intersection in the
problem $Part_{n,k}$ of testing whether $k$ subsets of $[n]$ form a partition.
It follows that the communication complexity, in the Number On the Forehead
(NOF) model, of $Part_{n,k}$, is equal to the minimal size of a partition of
$[k]^n$ into subsets that do not contain a combinatorial line. Thus, the bound
in \cite{chattopadhyay2007languages} on $Part_{n,k}$ using the Hales-Jewett
theorem is in fact tight, and the density Hales-Jewett number can be thought of
as a quantity in communication complexity. This gives a new angle to this well
studied quantity.
As a simple application we prove a lower bound on $c_{n,k}$, similar to the
lower bound in \cite{polymath2010moser} which is roughly $c_{n,k}/k^n \ge
\exp(-O(\log n)^{1/\lceil \log_2 k\rceil})$. This lower bound follows from a
protocol for $Part_{n,k}$. It is interesting to better understand the
communication complexity of $Part_{n,k}$ as this will also lead to the better
understanding of the Hales-Jewett number. The main purpose of this note is to
motivate this study.