9
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Density Hales-Jewett and Moser numbers

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

For any $$n \geq 0$$ and $$k \geq 1$$, the \emph{density Hales-Jewett number} $$c_{n,k}$$ is defined as the size of the largest subset of the cube $$[k]^n$$ := $$\{1,...,k\}^n$$ which contains no combinatorial line; similarly, the Moser number $$c'_{n,k}$$ is the largest subset of the cube $$[k]^n$$ which contains no geometric line. A deep theorem of Furstenberg and Katznelson shows that $$c_{n,k}$$ = $$o(k^n)$$ as $$n \to \infty$$ (which implies a similar claim for $$c'_{n,k}$$); this is already non-trivial for $$k = 3$$. Several new proofs of this result have also been recently established. Using both human and computer-assisted arguments, we compute several values of $$c_{n,k}$$ and $$c'_{n,k}$$ for small $$n,k$$. For instance the sequence $$c_{n,3}$$ for $$n=0,...,6$$ is $$1,2,6,18,52,150,450$$, while the sequence $$c'_{n,3}$$ for $$n=0,...,6$$ is $$1,2,6,16,43,124,353$$. We also prove some results for higher $$k$$, showing for instance that an analogue of the LYM inequality (which relates to the $$k = 2$$ case) does not hold for higher $$k$$, and also establishing the asymptotic lower bound $$c_{n,k} \geq k^n \exp(- O(\sqrt[\ell]{\log n}))$$ where $$\ell$$ is the largest integer such that $$2k > 2^\ell$$.

### Most cited references3

• Record: found

### Ein Satz �ber Untermengen einer endlichen Menge

(1928)
Bookmark
• Record: found

### A density version of the Hales-Jewett theorem

(1991)
Bookmark
• Record: found

### Primitive recursive bounds for van der Waerden numbers

(1988)
Bookmark

### Author and article information

###### Journal
01 February 2010
2010-04-25
###### Article
1002.0374