2010/02/02 by D. H. J. Polymath, Polymath, D. H. J. · 1 citation
Mathematics · #05D05 #05D10 #Advanced Combinatorial Mathematics #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1002.0374
openalex publication_date 2010/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For any n ≥ 0 and k ≥ 1, the density Hales-Jewett number cn,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 cn,k = o(kn) as n → ∞ (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 cn,k and c'n,k for small n,k. For instance the sequence cn,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 cn,k ≥ kn exp(- O(√[ℓ]log n)) where ℓ is the largest integer such that 2k > 2^ℓ.