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 = 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 [7] 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 co, similar to the lower bound in [19] which is roughly co(n,k)/k(n) = exp(-O(logn)(1/[log2k])). 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. (C) 2018 Elsevier B.V. All rights reserved.
展开▼
