general.hpp File Reference

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.)

Create milestones.
Hales-Jewett 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 t-tuples 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 non-degenerated.
  • So the hypergraphs are (V_t^N, E_t^N), where the hyperedges are the t-subsets 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}^{t-1} binomial(t,i) * N^i, where i stands for the number of degeneration-coordinates.
  • The Hales-Jewett 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 r-colourable.
  • 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 base-t-representation 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 line-lengths 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 d-dimensional "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 Hales-Jewett numbers: http://michaelnielsen.org/polymath1/index.php
    1. So there is actually considerable interest in computing Hales-Jewett numbers!
    2. 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.
    3. At http://michaelnielsen.org/polymath1/index.php?title=Hales-Jewett_theorem we find likely the most up-to-date bounds.
    4. halesjewett_r(3):
      1. r=3: > 13
      2. r=4: > 37
      3. r=5: > 84
      4. r=6: > 103
      5. These case use vanderwaerden_r(3).
    5. halesjewett_r(4):
      1. r=2: > 11
      2. r=3: > 97
      3. r=4: > 349
      4. r=5: > 751
      5. r=6: > 3259
      6. These case use vanderwaerden_r(4).
    6. halesjewett_r(5):
      1. r=2: > 59
      2. r=3: > 302
      3. r=4: > 2609
      4. r=5: > 6011
      5. r=6: > 14173
      6. These case use vanderwaerden_r(5).
    7. halesjewett_r(6):
      1. r=2: > 226
      2. r=3: > 1777
      3. r=4: > 18061
      4. r=5: > 49391
      5. r=6: > 120097
      6. These case use vanderwaerden_r(6).
    8. halesjewett_r(7):
      1. r=2: > 617
      2. r=3: > 7309
      3. r=4: > 64661
      4. These case use vanderwaerden_r(7).
    9. halesjewett_r(8):
      1. r=2: > 1069
      2. r=3: > 34057
      3. These case use vanderwaerden_r(8).
    10. halesjewett_r(9):
      1. r=2: > 3389
      2. These case use vanderwaerden_r(9).
    11. 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.
    12. 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.
    13. Precise values are known for 0 <= n <= 6: 1,2,6,18,52,150,450.
    14. A simple greedy algorithm is given there, but his works only up to n <= 3.
    15. Apparently their main algorithm is a genetic one: http://michaelnielsen.org/polymath1/index.php?title=Genetic_algorithm
    16. We must really work on hypergraph transversal algorithms!
    17. The general case is considered at http://michaelnielsen.org/polymath1/index.php?title=Higher-dimensional_DHJ_numbers where the notation c_{n,k} = alpha_halesjewett_hg(k,n)) is used.
    18. A simple upper bound is c_{n,k} <= (k-1)*k^{n-1}; parameter pairs where this upper bound is attained are called "saturated".

Definition in file general.hpp.