ﻻ يوجد ملخص باللغة العربية
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 krceil})$. 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.
The Hales-Jewett theorem for alphabet of size 3 states that whenever the Hales-Jewett cube [3]^n is r-coloured there is a monochromatic line (for n large). Conlon and Kamcev conjectured that, for any n, there is a 2-colouring of [3]^n for which there
We study the multiparty communication complexity of high dimensional permutations, in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where thr
A conjecture of Leader, Russell and Walters in Euclidean Ramsey theory says that a finite set is Ramsey if and only if it is congruent to a subset of a set whose symmetry group acts transitively. As they have shown the ``if direction of their conject
In this paper we initiate the study of property testing in simultaneous and non-simultaneous multi-party communication complexity, focusing on testing triangle-freeness in graphs. We consider the $textit{coordinator}$ model, where we have $k$ players
Information-theoretic methods have proven to be a very powerful tool in communication complexity, in particular giving an elegant proof of the linear lower bound for the two-party disjointness function, and tight lower bounds on disjointness in the m