General plans regarding investigations on Ramsey theory (Ramsey problems, van der Waerden problems, etc.)
More...
Go to the source code of this file.
Detailed Description
General plans regarding investigations on Ramsey theory (Ramsey problems, van der Waerden problems, etc.)
 Todo:
 Create milestones.
 Todo:
 Connections
 Todo:
 HalesJewett problems

The length k of arithmetic progressions is now called t.

And N now stands for the "dimension" of the set of vertices, while its size is n = t^N.

And the vertices are not arbitrary elements but the elements of V_t^N := {1,...,t}^N.

Instead of an arithmetic progression now "lines" are considered, which are ttuples of elements of V such that for each coordinate we have a possibly degenerated (ascending) arithmetic progression ("degenerated" allows slope 0), where for at least one coordinate the arithmetic progression (which must be just (1,...,t)) is nondegenerated.

So the hypergraphs are (V_t^N, E_t^N), where the hyperedges are the tsubsets of V such that an ordering exists making this subset to a "line" (such an ordering is then unique).

We have E_t^N = sum_{i=0}^{t1} binomial(t,i) * N^i, where i stands for the number of degenerationcoordinates.

The HalesJewett theorem now asserts the existence of halesjewett_r(t) = N, so that N' >= N is equivalent to the hypergraph (V_t^N, E_t^N) not being rcolourable.

We have vanderwaerden_r(t) <= t^halesjewett_r(t), since using the bijection from {1,...,n} to V_t^N given by interpreting the elements of V_t^n as basetrepresentation of natural numbers, but where we have to subtract 1 from each such digit, lines yield special arithmetic progressions.

It seems not possible to create natural "mixed forms", since for different linelengths t we have to use different vertices (namely tuples over {1,..,t}).

On the other hand, using the notion of arithmetic progression as we did it, one could for example consider arithmetic progressions in a base set {1,...,T} with T = max {t_1,...,t_r} of slope 0 or 1 (i.e., in each coordinate we must have such an arithmetic progression, and where at least for one coordinate the slope is 1).

There is a generalisation halesjewett_r^d(t), where d=1 for the above form, and where instead of lines ddimensional "subspaces" are considered.


It is known that halesjewett_r(2) = r.

Likely we should create a new module ComputerAlgebra/RamseyTheory/Lisp/HalesJewett.

There is a project about HalesJewett numbers: http://michaelnielsen.org/polymath1/index.php

So there is actually considerable interest in computing HalesJewett numbers!

We have http://www.math.ucsd.edu/~etressle/hj32.pdf, where halesjewett_2(3) = 4 is shown, directly with a proof by case distinctions, and mentioning also an algorithm.

At http://michaelnielsen.org/polymath1/index.php?title=HalesJewett_theorem we find likely the most uptodate bounds.

halesjewett_r(3):

r=3: > 13

r=4: > 37

r=5: > 84

r=6: > 103

These case use vanderwaerden_r(3).

halesjewett_r(4):

r=2: > 11

r=3: > 97

r=4: > 349

r=5: > 751

r=6: > 3259

These case use vanderwaerden_r(4).

halesjewett_r(5):

r=2: > 59

r=3: > 302

r=4: > 2609

r=5: > 6011

r=6: > 14173

These case use vanderwaerden_r(5).

halesjewett_r(6):

r=2: > 226

r=3: > 1777

r=4: > 18061

r=5: > 49391

r=6: > 120097

These case use vanderwaerden_r(6).

halesjewett_r(7):

r=2: > 617

r=3: > 7309

r=4: > 64661

These case use vanderwaerden_r(7).

halesjewett_r(8):

r=2: > 1069

r=3: > 34057

These case use vanderwaerden_r(8).

halesjewett_r(9):

r=2: > 3389

These case use vanderwaerden_r(9).

Also the density considerations are of interest, since the hypergraphs sequences have the density property, i.e., the quotients alpha_halesjewett_hg(k,N)) / k^N > 0 for fixed k.

For k=3 these independence numbers are studied at http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds where c_n = alpha_halesjewett_hg(3,n)) is used.

Precise values are known for 0 <= n <= 6: 1,2,6,18,52,150,450.

A simple greedy algorithm is given there, but his works only up to n <= 3.

Apparently their main algorithm is a genetic one: http://michaelnielsen.org/polymath1/index.php?title=Genetic_algorithm

We must really work on hypergraph transversal algorithms!

The general case is considered at http://michaelnielsen.org/polymath1/index.php?title=Higherdimensional_DHJ_numbers where the notation c_{n,k} = alpha_halesjewett_hg(k,n)) is used.

A simple upper bound is c_{n,k} <= (k1)*k^{n1}; parameter pairs where this upper bound is attained are called "saturated".
Definition in file general.hpp.