Outline of second paper: Difference between revisions
| Line 15: | Line 15: | ||
For any <math>n \geq 0</math> and <math>k \geq 1</math>, the density Hales-Jewett number <math>c_{n,k}</math> is defined as the size of the largest subset of the cube <math>[k]^n := \{1,\ldots,k\}^n</math> which contains no combinatorial line; similarly, the Moser number <math>c'_{n,k}</math> is the largest subset of the cube <math>[k]^n</math> which contains no geometric line. A deep theorem of Furstenberg and Katznelson [cite] shows that <math>c_{n,k} = o(k^n)</math> as <math>n \to \infty</math> (which implies a similar claim for <math>c'_{n,k}</math>; this is already non-trivial for <math>k=3</math>. Several new proofs of this result have also been recently established [cite Polymath], [cite Austin]. | For any <math>n \geq 0</math> and <math>k \geq 1</math>, the density Hales-Jewett number <math>c_{n,k}</math> is defined as the size of the largest subset of the cube <math>[k]^n := \{1,\ldots,k\}^n</math> which contains no combinatorial line; similarly, the Moser number <math>c'_{n,k}</math> is the largest subset of the cube <math>[k]^n</math> which contains no geometric line. A deep theorem of Furstenberg and Katznelson [cite] shows that <math>c_{n,k} = o(k^n)</math> as <math>n \to \infty</math> (which implies a similar claim for <math>c'_{n,k}</math>; this is already non-trivial for <math>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>c_{n,k}</math> and <math>c'_{n,k}</math> for small <math>n,k</math>. For instance the sequence <math>c_{n,3}</math> for <math>n=0,\ldots,6</math> is <math>1,2,6,18,52,150,450</math>, while the sequence <math>c'_{n,3}</math> for <math>n=0,\ldots,5</math> is <math>1,2,6,16,43,124</math>. We also establish some results for higher <math>k</math>, showing for instance that an analogue of the LYM inequality (which relates to the <math>k=2</math> case) does not hold for higher <math>k</math>. | Using both human and computer-assisted arguments, we compute several values of <math>c_{n,k}</math> and <math>c'_{n,k}</math> for small <math>n,k</math>. For instance the sequence <math>c_{n,3}</math> for <math>n=0,\ldots,6</math> is <math>1,2,6,18,52,150,450</math>, while the sequence <math>c'_{n,3}</math> for <math>n=0,\ldots,5</math> is <math>1,2,6,16,43,124,353</math>. We also establish some results for higher <math>k</math>, showing for instance that an analogue of the LYM inequality (which relates to the <math>k=2</math> case) does not hold for higher <math>k</math>. | ||
== Sections == | == Sections == | ||
Revision as of 23:53, 11 July 2009
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 [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,353 }[/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. But the six-point examples will get mentioned a lot.
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]
Connection between Moser[math]\displaystyle{ (n,2k) }[/math] and DHJ[math]\displaystyle{ (n,k) }[/math]
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
- polymath.tex
- introduction.tex
- dhj-lown.tex
- dhj-lown-lower.tex
- moser.tex
- moser-lower.tex
- fujimura.tex
- higherk.tex
- genetic.tex
- integer.tex
- coloring.tex
- A figure depicting combinatorial lines
- A figure depicting geometric lines
- A figure depicting a 353-point 6D Moser set
The above are the master copies of the LaTeX files. Below are various compiled versions of the source:
