2017/06/07 by Shraibman, Adi
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1706.02277
For integers n and k, the density Hales-Jewett number cn,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 cn,k is equal to the maximal size of a cylinder intersection in the problem Partn,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 Partn,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 \citechattopadhyay2007languages on Partn,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 cn,k, similar to the lower bound in \citepolymath2010moser which is roughly cn,k/kn ≥ exp(-O(log n)1/\lceil log2 k\rceil). This lower bound follows from a protocol for Partn,k. It is interesting to better understand the communication complexity of Partn,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.