| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Density Hales-Jewett and Moser numbers | D.H.J. Polymath
; | Date: |
2 Feb 2010 | 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 o 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$. | Source: | arXiv, 1002.0374 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |