Outline of second paper

Here is a proposed outline of the second paper, which will focus on the new bounds on DHJ(3) and Moser numbers, and related quantities.

Metadata

Author: D.H.J. Polymath
Address: http://michaelnielsen.org/polymath1/index.php (Do we need a more stable address?)
Email: ???
Title: Density Hales-Jewett and Moser numbers in low dimensions.
AMS Subject classification: ???

Abstract

(A draft proposal - please edit)

For any [math]\displaystyle{ n \geq 0 }[/math] and [math]\displaystyle{ k \geq 1 }[/math], the density Hales-Jewett number [math]\displaystyle{ c_{n,k} }[/math] is defined as the size of the largest subset of the cube [math]\displaystyle{ [k]^n := \{1,\ldots,k\}^n }[/math] which contains no combinatorial line; similarly, the Moser number [math]\displaystyle{ c'_{n,k} }[/math] is the largest subset of the cube [math]\displaystyle{ [k]^n }[/math] which contains no geometric line. A deep theorem of Furstenberg and Katznelson [cite] shows that [math]\displaystyle{ c_{n,k} = o(k^n) }[/math] as [math]\displaystyle{ n \to \infty }[/math] (which implies a similar claim for [math]\displaystyle{ c'_{n,k} }[/math]; this is already non-trivial for [math]\displaystyle{ k=3 }[/math]. Several new proofs of this result have also been recently established [cite Polymath], [cite Austin].

Using both human and computer-assisted arguments, we compute several values of [math]\displaystyle{ c_{n,k} }[/math] and [math]\displaystyle{ c'_{n,k} }[/math] for small [math]\displaystyle{ n,k }[/math]. For instance the sequence [math]\displaystyle{ c_{n,3} }[/math] for [math]\displaystyle{ n=0,\ldots,6 }[/math] is [math]\displaystyle{ 1,2,6,18,52,150,450 }[/math], while the sequence [math]\displaystyle{ c'_{n,3} }[/math] for [math]\displaystyle{ n=0,\ldots,5 }[/math] is [math]\displaystyle{ 1,2,6,16,43,124 }[/math]. We also establish some results for higher [math]\displaystyle{ k }[/math], showing for instance that an analogue of the LYM inequality (which relates to the [math]\displaystyle{ k=2 }[/math] case) does not hold for higher [math]\displaystyle{ k }[/math].

Sections

Introduction

Basic definitions. Definitions and notational conventions include

[k] = {1, 2, ..., k}
Subsets of [k]^n are called A
definition of combinatorial line, geometric line
Hales-Jewett numbers, Moser numbers

History of and motivation for the problem:

Sperner's theorem
Density Hales-Jewett theorem, including new proofs
Review literature on Moser problem

New results

Computation of several values of [math]\displaystyle{ c_{n,3} }[/math]
Computation of several values of [math]\displaystyle{ c'_{n,3} }[/math]
Asymptotic lower bounds for [math]\displaystyle{ c_{n,k} }[/math]
Genetic algorithm lower bounds
Some bounds for [math]\displaystyle{ c_{n,k} }[/math] for low n and large k
Connection between Moser(2k) and DHJ(k)
Hyper-optimistic conjecture, and its failure
New bounds for colouring Hales-Jewett numbers

Lower bounds for density Hales-Jewett

Fujimura implies DHJ lower bounds; some selected numerics (e.g. lower bounds up to 10 dimensions, plus a few dimensions afterwards).

The precise asymptotic bound of [math]\displaystyle{ c_{n,k} \gt C k^{n - \alpha(k)\sqrt[\ell]{\log n}+\beta(k) \log \log n} }[/math]

Discussion of genetic algorithm

Low-dimensional density Hales-Jewett numbers

Very small n

[math]\displaystyle{ n=0,1,2 }[/math] are trivial.

For [math]\displaystyle{ n=3 }[/math], one needs to classify the 17-point and 18-point examples.

n=4

One needs to classify the 50-point, 51-point, and 52-point examples.

n=5

This is the big section, showing there are no 151-point examples.

n=6

Easy corollary of n=5 theory

Higher k DHJ numbers

Exact computations of [math]\displaystyle{ c_{2,k}, c_{3,k} }[/math]

Numerics

Failure of hyper-optimistic conjecture

Lower bounds for Moser

Using sphere packing to get lower bounds

Implications between Moser and DHJ

Moser in low dimensions

There is some general slicing lemma that needs to be proved here that allows inequalities for low-dim Moser to imply inequalities for higher dim.

For n=0,1,2 the theory is trivial.

For n=3 we need the classification of Pareto optimal configurations etc. So far this is only done by computer brute force search; we may have to find a human version.

n=4 theory: include both computer results and human results

n=5: we have a proof using the n=4 computer data; we should keep looking for a purely human proof.

n=6: we can give the partial results we have.

Fujimura's problem

Coloring DHJ

Files

The above are the master copies of the LaTeX files. Below are various compiled versions of the source:

Outline of second paper

Contents