Outline of second paper

From Polymath1Wiki

Revision as of 16:27, 23 January 2010 by Teorth (Talk | contribs)

(diff) ←Older revision | Current revision (diff) | Newer revision→ (diff)

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
AMS Subject classification: ???

Abstract

(A draft proposal - please edit)

For any $n \geq 0$ and $k \geq 1$ , the density Hales-Jewett number $c n, k$ is defined as the size of the largest subset of the cube $[k]^n := \{1,\ldots,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 [cite] 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 [cite Polymath], [cite Austin].

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,\ldots,6$ is $1,2,6,18,52,150,450$ , while the sequence $c' n,3$ for $n=0,\ldots,6$ is $1,2,6,16,43,124,353$ . We also establish 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$ .

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 $c n,3$
Computation of several values of $c' n,3$
Asymptotic lower bounds for $c n, k$
Genetic algorithm lower bounds
Some bounds for $c n, k$ 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
Kakeya problem for $Z_3^n$

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 $c_{n,k} > C k^{n - \alpha(k)\sqrt[\ell]{\log n}+\beta(k) \log \log n}$

Discussion of genetic algorithm

Low-dimensional density Hales-Jewett numbers

Very small n

$n = 0,1,2$ are trivial. But the six-point examples will get mentioned a lot.

For $n = 3$ , 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 $c 2, k, c 3, k$

Connection between Moser $(n,2 k)$ and DHJ $(n, k)$

Numerics

Failure of hyper-optimistic conjecture

Lower bounds for Moser

Using Gamma sets to get lower bounds

Adding extra points from degenerate triangles

Higher k; 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: